[C] Algoritmo numeri primi

[MrX87]

Ciao, parlando con il mio prof dei numeri primi, mi ha detto che c'è un algoritmo che permette di identificare i numeri primi da 1-N...in poche parole bisogna partire da 2 e eliminare tutti i suoi multipli fino a N, poi passare a 3 e fare la stessa cosa...fino a quando nn c sn più multipli...ecco...io ho provato a riportare questo in C...ma non con grandissimo successo...perchè sembra che il programma funzioni solo se inserisco N<=9...se metto N>9 va in crash...però io non ho capito per quale motivo...posto qua il codice...sperando che almeno qualcosa d sensato l'ho scritta...

/*Algoritmo numeri primi*/

#include <stdio.h>
#include <stdlib.h>

void primi ( int*, int* );
void del ( int*, int*);

int main ()
{
	int *vet, dim;
	int i;
	
	printf ("Numero elementi del vettore: ");
	scanf  ("%d", &dim);

	vet = (int *) malloc ( (dim+1) * sizeof(int));

	if ( vet == NULL ) { 
		printf ("Errore allocazione!!\n");
		return 0;
	}		
	
	for ( i=1; i<=dim; i++ ) 
		vet[i]=i;

	primi ( vet, &dim);

	for ( i=2; i<=dim; i++ )
		printf ("%4d", vet[i]);
	
	printf ("\n");
	free(vet);
	return 0;
}
void primi ( int* v, int *size)
{
	int x, y;

	for ( x=2; x<=*size; x++ ) {
		for ( y=x+1; y<=(*size); y++ ) {
			if ( (v[y]%v[x]) == 0 ) 
				v[y]=0;
		}
		del ( v, &(*size));
	}
}
void del ( int *v2, int *dim ) 

{

     int x, y, flag=0;


     for ( x=2; x<=(*dim) && flag==0; x++ ) {

        if ( v2[x] == 0 ) {

                flag=1;

                for ( y=x; y<=(*dim)-1; y++ ) {

                    v2[y] = v2[y+1];

                }

        (*dim)--;        

        }    

    }

}

[oregon]

Il problema e' in questa riga

if ( (v[y]%v[x]) == 0 )

... da un certo punto in poi, v[x] diventa zero e la divisione per zero genera il crash.

Comunque, non capisco perche' utilizzi un vettore per la ricerca dei numeri primi ...

[MrX87]

ah...si...infatti...non ci avevo fatto caso...comunque...si potrebbe fare senza utilizzare un vettore??

[oregon]

Ovviamente sì ... dato che devi solo visualizzare i numeri primi man mano che li trovi, non c'e' necessita' di memorizzarli in un vettore ...

[MrX87]

un'altra cosa...l'utilizzo della funzione malloc() è esatto??

[MrX87]

però...aspetta un secondo...

l problema e' in questa riga

if ( (v[y]%v[x]) == 0 )

... da un certo punto in poi, v[x] diventa zero e la divisione per zero genera il crash.

ma...scusa, non dovrebbe mica fare la divisione per 0...io gli zeri li caccio con la funz del()...

[oregon]

Ho solamente visto, con un po' di debug, che il problema si verifica con una divisione per zero in quella linea. Non ho approfondito, quindi non so se

1) il tuo algoritmo non e' corretto

2) hai sbagliato qualcosa nella funzione del

3) hai sbagliato qualcosa nei cicli for

P.S. La malloc va bene perche' tu tratti gli elementi che vanno da 1 al massimo del vettore

[MrX87]

okay...errore trovato...era nella funz del...che ho preso con molta fiducia da un programma che avevo fatto qualche tempo fa...pensando che faceva il suo lavoro esattamente, invece, eliminava solo il primo 0 che incontrava nel vettore...e lasciava gli altri...quindi si verificava la divizione per 0 e andava in crash...comunque posto lo stesso il codice, che dovrebbe funzionare...e intanto penso ad un modo per fare l'esercizio senza usare il vettore...

/*Algoritmo numeri primi*/

#include <stdio.h>
#include <stdlib.h>

void primi ( int*, int* );
void del ( int*, int*);

int main ()
{
	int *vet, dim;
	int i, N;
	
	printf ("Numero elementi del vettore: ");
	scanf  ("%d", &dim);
    N = dim;
	vet = (int *) malloc ( (dim+1) * sizeof(int));

	if ( vet == NULL ) { 
		printf ("Errore allocazione!!\n");
		return 0;
	}		
	
	for ( i=1; i<=dim; i++ ) 
		vet[i]=i;

	primi ( vet, &dim);

    printf ("Sequenza numeri primi da 1-%d\n", N);
	for ( i=2; i<=dim; i++ )
		printf ("%4d", vet[i]);
	
	printf ("\n");
	free(vet);
	system("pause");
	return 0;
}
void primi ( int* v, int *size)
{
	int x, y;

	for ( x=2; x<=*size; x++ ) {
		for ( y=x+1; y<=(*size); y++ ) {
			if ( (v[y]%v[x]) == 0 ) 
				v[y]=0;
		}
		del ( v, &(*size) );
	}
}
void del ( int *v2, int *dim ) 
{
    int x, y;

    for ( x=2; x<=(*dim); x++ ) {
        if ( v2[x] == 0 ) {
           for ( y=x; y<=(*dim)-1; y++ ) {
               v2[y] = v2[y+1];
           }
           (*dim)--;
           x--;        
        }    
    }

}

[MrX87]

Comunque, non capisco perche' utilizzi un vettore per la ricerca dei numeri primi ...

Sembra che ci sono riuscito a farlo senza vettore...posto il codice vediamo se va bene o se almeno è come lo pesavi tu...

#include <stdio.h>
#include <stdlib.h>

int main ()
{
    int dim;
    int i, j, flag=0;
    
    printf ("Inserire valore(maggiore di 2): ");
    scanf  ("%d", &dim);
    
    for ( i=2; i<=dim; i++ ) {
        flag=0;
        for ( j=2; j<i && flag==0; j++ ) {
            if ( (i%j) == 0 )
               flag=1;
        }
        if ( flag == 0 )
           printf ("%4d", i);
    }
    printf ("\n");
    system ("pause");
}

[MrX87]

grazie mille per gli aiuti...comunque ho parlato con il mio prof e mi ha detto che andrebbe anche bene così...