[C] Crivello di Eratostene

[xbubbax]

Qualcuno mi sa dire perchè non funziona questo programma? E' stato più facile del previsto farlo, ma non funge

#include <stdio.h>
#define SIZE 20

int main(){

int n;
int a[SIZE];
int i;
int j=2;

for(i=0;i<SIZE;i++){
a[i]=1;}

printf("Inserisci un intero n:\n");
scanf("&d", &n);
for(j=2;j<n;j++){
for(i=2;i<=n;i++){
if((i!=j)&&((i%j)==0)){
a[i]=0;}}}
for(i=0;i<n;i++){
if(a[i]==1){
printf("%d\n", a[i]);}}}

[xbubbax]

Il programma deve trovare i numeri primi da 1 a n

[pisto]

è il primo thread su C a cui rispondo, potrei dir cazzate... ho incominciato a guardarmi il C ieri e sto ancora tribolando ad installare il compilatore quindi non posso testare..

cmq: prima di tutto il tuo programma crea un array di dimensione fissa, quindi evidentemente non può trovare i numeri primi fino ad n ad ogni valore di n. quindi la lunghezza dell'array che crei deve dipendere da n.

poi, nei for che fanno effettivamente il crivello ti complichi la vita, basterebbe moltiplicare j da 2 in poi (controllare che il risultato non sia superiore alla lunghezza dell'array) e mettere 0 nel rispettivo indice dell'array ottenuto da questa operazione. attualmente con il tuo programma rischi di superare il limite dell'array fino al quadrato della sua dimensione!

ci sarebbero altre ottimizzazioni, ma per adesso guarda se con queste correzioni va.

[mapomapo]

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

void main()
{

int n;
int *a;
int i;
int j=2;

printf("Inserisci un intero n: ");
scanf("%d", &n);

a = (int *)malloc((n+2)*sizeof(int));

for(i=0;i<n;i++)
a[i]=1;

for(j=2;j<n;j++)
for(i=2;i<n;i++)
if( (i != j) && ( (i%j)==0 ) )
a[i]=0;


for(i=2;i<n;i++)
if(a[i]==1)
printf("%d ", i);
printf("\n");

}


Ho provato a riscriverlo visto che non capivo bene la tua logica, scusami ma sono abituato così :)
il mio programmino lavora in questa maniera:
-Acquisisce il numero n secondo il criterio di Eratostene
-Alloca un vettore di n+2 elementi (così posso lavorare sull'indice del vettore!)
-Esegue un paio di for annidati e credo in questo caso operi secondo la tua stessa logica.

Vito

[pisto]

for(j=2;j<n;j++)
for(i=2;i<n;i++)
if( (i != j) && ( (i%j)==0 ) )
a[i]=0;


sì in effetti ho detto una cazzata, così funziona perfettamente questa parte, non va oltre il limite dell'array.
però, non sarebbe molto + semplice una cosa tipo:

for(j=2;j<=n/2;j++){
for(i=2;i<=n/j;i++){
a[i]=0;
}
}

[LetBloodline]

sì in effetti ho detto una cazzata, così funziona perfettamente questa parte, non va oltre il limite dell'array.
però, non sarebbe molto + semplice una cosa tipo:

for(j=2;j<=n/2;j++){
for(i=2;i<=n/j;i++){
a[i]=0;
}
}


Ma così metti a 0 tutti gli elementi dell'array da 2 a n/2 Oo

for(i=2;i<=n/j;i++){
a[i]=0;
nella prima interazione j vale 2 e avremo
for(i=2;i<=n/2,i++){
a[i]=0;
Prende tutta la prima metà dell'array e la mette a 0 a partire dall'indice 2, compresi 3 5 7 9 etc

[Furla]

il verbo "Indentare" ti dice nulla?
faresti un favore a te e agli altri, se rendessi il tuo codice leggibile:



int main()
{
int n;
int a[SIZE];
int i;
int j=2;

for(i=0;i<SIZE;i++)
a[i]=1;

printf("Inserisci un intero n:\n");
scanf("%d", &n);

for(j=2; j<n; j++)
for(i=2; i<=n; i++)
if(i!=j && i%j==0)
a[i]=0;

for(i=0; i<n; i++)
if(a[i]==1)
printf("%d\n", a[i]);
}

prima di tutto le parentesi graffe le puoi togliere, quando il corpo del costrutto prevede una sola istruzione: in quei casi appesantiscono e confondono la lettura.

poi tu usi un array di interi, ma li usi come flag binari. potresti usare il tipo char per ottimizzare lo spazio, o addirittura usare un solo bit per numero giocando con maschere e shift. inoltre usi un array di dimensione fissa senza alcun controllo sul numero inserito: o aggiungi il controllo o allochi dinamicamente l'array per "adeguarlo" a quel numero.

nell'ultimo for controlli che a[i] sia uno, e se è così lo stampi... ovvio che il programma stampi a video una serie di "1"... quello che volevi fare era stampare gli indici i per i quali il flag è rimasto a 1 dopo l'applicazione del crivello.

[xbubbax]

Grazie mille per le risposte

Tra un'oretta le comincio a guardare, ora sono impegnato in un altro programmino:D

[xbubbax]

scusate ma non so proprio come incollarlo bene, come fate voi

comq ho modificato una cosetta ma come risultato mi da 1, non capisco dove sbaglio


#include <stdio.h>
#define SIZE 20

int main(){

int n;
int a[n];
int i;
int j=2;

printf("Inserisci un intero n:\n");
scanf("&d", &n);

for(i=0;i<n;i++){
a[i]=1;}


for(j=2;j<n;j++){
for(i=2;i<=n;i++){
if((i!=j)&&((i%j)==0)){
a[i]=0;}}}
for(i=0;i<n;i++){
if(a[i]==1){
printf("%d\n", a[i]);}} }

[xbubbax]

ho modificato un'altra cosetta e ora mi da 0 e 1 come risultato

#include <stdio.h>
#define SIZE 20

int main(){

int n;
int a[n];
int i;
int j=2;

printf("Inserisci un intero n:\n");
scanf("&d", &n);

for(i=0;i<n;i++){
a[i]=1;}


for(j=2;j<n;j++){
for(i=2;i<=n;i++){
if((i!=j)&&((i%j)==0)){
a[i]=0;}}}
for(i=0;i<n;i++){
if(a[i]==1){
printf("%d\n", i);}}

[pisto]

cribbio, volevo dire:
for(j=2;j<=n/2;j++){
for(i=2;i<=n/j;i++){
a[j*i]=0;
}
}
il che è mooolto più veloce dell'iterazione di bubba

edit: facendo dei test in java: col mio metodo fino a 10000000 ci vogliono col mio 13.5 secondi, col suo.... sta ancora girando XD

[xbubbax]

ho provato a mettere il pezzo che dici tu ma mi da sempre 0 e 1, come se il 2,3,5 ecc..non li conta come primi, forse sbaglio quando stampo il risultato

#include <stdio.h>
#define SIZE 20

int main(){

int n;
int a[n];
int i;
int j=2;

printf("Inserisci un intero n:\n");
scanf("&d", &n);

for(i=0;i<n;i++){
a[i]=1;}


for(j=2;j<=n/2;j++){
for(i=2;i<=n/j;i++){
a[j*i]=0;
}
}
for(i=0;i<n;i++){
if(a[i]==1){
printf("%d\n", i);}}

[pisto]

la parte di codice che stampa è corretta, almeno come hai costruito il ciclo for, credo che sia qualcosa che non va in "printf("%d\n", i)", ma non ti so aiutare, io di c sto ancora a dichiarazione e definizione, include etcetera

edit: prova a mettere printf("%d", i)
edit2: segui il consiglio di Furla, cioè di alleggerire l'array...
edit3: aspetta, ma tu mi stai dicendo che ti stampa 0 e 1, e poi la serie corretta? allora basta che modifichi il ciclo di stampa così:

for(i=2;i<n;i++)
if(a[i]==1)
printf("%d", i);

[mastoo]

ho provato a mettere il pezzo che dici tu ma mi da sempre 0 e 1, come se il 2,3,5 ecc..non li conta come primi, forse sbaglio quando stampo il risultato

#include <stdio.h>
#define SIZE 20

int main(){

int n;
int a[n]; é qui il problema
int i;
int j=2;

printf("Inserisci un intero n:\n");
scanf("&d", &n);

for(i=0;i<n;i++){
a[i]=1;}


for(j=2;j<=n/2;j++){
for(i=2;i<=n/j;i++){
a[j*i]=0;
}
}
for(i=0;i<n;i++){
if(a[i]==1){
printf("%d\n", i);}}

il fatto è che quel vettore non ha una dimensione n come credi tu perche la variabile n non è stata inizializzata protrebbe contenere qualsiasi valore intero
devi fare come ti ha detto mapomapo o fai il vettore di dimensione fissa
cosi tipo

#include <stdio.h>
#define SIZE 20

main()
{

int a[SIZE+1];
int i, j;

for(i=0;i<SIZE;i++)
a[i]=1;


for(j=2;j<=SIZE/2;j++)
for(i=2;i<=SIZE/j;i++)
a[j*i]=0;


/*stampa*/
for(i=2;i<SIZE;i++)
if(a[i]==1)
printf("%d\n", i);


}

[xbubbax]

e volendo modificare il mio senza riscrivere tutto quel pezzo come posso fare?

cioè al poso di a[n] cosa dovrei metterci?

che significa fare un vettore di dimensioni fisse?

[pisto]

beh insomma ti è stato detto tutto quello che devi fare, adesso il codice lo butti giù tu, sei tu che devi imparare C no? devi trovare il modo per creare un array a runtime visto che il limite fino a quale cercare i numeri primi lo decidi a runtime, non stabilito in fase di compilazione.
guarda il codice di mapomapo

[xbubbax]

ho capito, non so se ci sarei arrivato però.. il mio mi sembrava perfetto:D