c stampare 100 numeri primi

[fenics]

devo svolgere un programma in c che mi stampi i primi 100 numeri primi:
così io ho fatto:

#include<stdio.h>

int main()
{
    int vet[100];
    int i, n;

    for(i=0; i<100; i++)
    {
        for(i=2; i<100; i++)
        {
            for(n=2; n<=100; n++)
            {
                if(vet[n%i]==1);
                vet[n%i]=1;
            }
        }
    }
}

e... ma poi non so continuare

[Alex'87]

Perché il triplo for? O_o

Comunque: un numero è primo se non ha divisori a parte 1 e se stesso. Dato un numero X ti basta quindi provare a dividerlo per tutti i numeri che vanno da 2 a X - 1. Se non hai mai resto 0 il numero è primo...

Come ottimizzazione puoi saltare i numeri pari e puoi fermarti alla radice quadrata di X.

[M.A.W. 1968]

L'algoritmo che stai cercando di implementare è talmente "nuovo" che era già noto ad Eratostene nel terzo secolo a.C.

Fai una bella ricerca sul tuo search engine preferito per "crivello di Eratostene": un'ottima occasione per imparare bene una tecnica algoritmica fondamentale, usata anche in centinaia di altre applicazioni analoghe. Il metodo naif delle divisioni successive è ovviamente il massimo dell'inefficienza.

[fenics]

infatti si tratta proprio di eratostene

[M.A.W. 1968]

infatti si tratta proprio di eratostene

Elementare, caro dottor Watson...

Ma cosa dice codesto algoritmo, certo non efficientissimo ma di facilissima implementazione, nella sua versione di base "carta-e-penna"?

Fissato un limite arbitrario intero positivo n (significativamente maggiore di due), si compila una tabella contenente ordinatamente tutti i numeri interi positivi strettamente compresi tra 2 e tale n. Quindi, per ogni intero positivo strettamente compreso tra 2 e la radice quadrata di n (approssimata per difetto all'intero, ovviamente!) si "cancellano" dalla tabella tutti i multipli di tale numero.
I numeri rimanenti dopo questa "setacciatura" sono tutti e soli i numeri primi compresi tra due (primo numero primo e unico primo pari) e il limite dato.

Tutto chiaro fino a qui? Quel "per ogni" si traduce ovviamente in un ciclo, e "tutti i multipli" in un secondo ciclo annidato.
Prova intanto ad implementare questa parte, usando uno zero per "cancellare" i valori compositi dalla tabella: per migliorie e ottimizzazioni c'è tempo e modo di procedere per gradi (le due più banali e macroscopiche: i numeri pari possono subito essere esclusi per costruzione, e la "tabella" può essere facilmente implementata come un array grossolanamente booleano, sebbene in modo poco efficiente in spazio).

[fenics]

come si fa la radice quadrata in c?? Cioè come la calcolo??

[Scara95]

sqrt da math.h

[fenics]

oddio, allora, io perora ho scannerizzato 2 cicli for annidati in questo modo

#include<stdio.h>

int main()
{
    int vet[100];
    int i, n;
    
    for(i=0; i<100; i++)
    {
        for(n=2; n<100; n++)
    }
}

[oregon]

Scannerizzato?

[fenics]

ho implementato questo codice per ora, la radice quadrata l'ho calcolata con la funzione pow. ditemi se fin quì va bene

#include<stdio.h>
#include<math.h>

int main()
{
    int vet[100];
    int i, n;

    for(i=2; i<100; i++)
    {
        for(n=2; n<=100; n++)
        {
            n=pow(100, 2.0f);
        }
    }
}