Crivello di Eratostene [C]

di
Nico517
il
5 risposte
N
Nico517
Pochi posts
Iscritto da
ago, 2015
Messaggi:
2

Crivello di Eratostene [C]

Salve a tutti! Ho iniziato a studiare il C da qualche mese e ho creato un programma che calcola tutti i numeri primi da 1 a 518158. Il problema e' che quando finisce il ciclo ho l'errore che il programma non risponde... Come posso risolvere?
Avrei da chiedervi altre due cose:
1) Posso aumentare il limite di 518158?
2) Se volessi creare un file di output come potrei fare?
Grazie

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

#define MAX 518158

int main(void) {
int v[MAX], i, j;

for (i=2; i<MAX; i++)
v = 1;
for (i=2; i<MAX; i++) {
if (v == 1) {
printf("%d\n", i);
for (j=2; i*j<MAX; j++)
v[i*j] = 0;
}
}
system("pause >nul");
return(0);
}

5 Risposte

  • Çlÿkÿ~
    Çlÿkÿ~
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    196

    Re: Crivello di Eratostene [C]

    0) non ne sono sicuro, ma credo che vada in errore perchè modifichi valori non consentiti all'interno dell'array. i e j arrivano fino a 518.157, quindi tu vai a modificare v[518.157*518.157].
    1) sì, puoi aumentare, ricordati però che l'intero massimo che puoi avere è di 2.147.483.647, se vuoi andare oltre devi utilizzare il long long int che ti tiene numeri fino a 9.223.372.036.854.775.807.
    (se vuoi ancora più numeri dichiari la variabile come unsigned, avrà soltanto valori assoluti e ti farà memorizzare il doppio dei numeri).
    2) anzichè usare una printf normale esegui una fprintf dentro al file in cui vuoi mettere l'output.
  • N
    Nico517
    Pochi posts
    Iscritto da
    ago, 2015
    Messaggi:
    2

    Re: Crivello di Eratostene [C]

  • Çlÿkÿ~
    Çlÿkÿ~
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    196

    Re: Crivello di Eratostene [C]

    Nico517 ha scritto:


    Mi faresti le modifiche al codice (o mi spiegheresti come farle) in modo da ottenere il punto 1 per piacere?
    prova a dichiarare v, i e j come long long int, poi setta MAX al valore che vuoi (la define credo prenda da sola il tipo; se ti dà problemi anzichè dichiarare MAX tramite define lo dichiari nel main, sempre come long long int).
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6072

    Re: Crivello di Eratostene [C]

    Attenzione:
    1) lo stack NON HA dimensione infinita! Sono 1 o 2MB (da controllare perche' dipende dal compilatore/sistema operativo/configurazioni varie)!

    Quindi, ad esempio, allocare un vettore di 500.000 interi (4 byte) vuol dire REMPIRE l'INTERO STACK!!!!! Con conseguenze non facilmente prevedibili.

    2) v[i*j] e' sbagliato!
    3) e' sbagliata anche la parte di ciclo che utilizza v[i*j]!

    Rileggi come funziona il crivello di eratostene!
  • W
    Wolt
    Utente Attivo
    Iscritto da
    lug, 2013
    Messaggi:
    111

    Re: Crivello di Eratostene [C]

    Inoltre da quanto ho capito vuoi usare v per assegnare ai numeri primi il valore 1 e ai non primi il valore 0, quindi perché non dichiararlo direttamente come un array di booleani (ti basterebbe fare solo qualche semplice calcolo per capire il risparmio ottenuto)?

    PS: Evita di sprecare v[0] e v[1]...
Devi accedere o registrarti per scrivere nel forum
5 risposte