Imprimă pagina - numere prime

Titlul: numere prime
Scris de: Prehari Romica din Ianuarie 12, 2013, 14:01:37

Buna, as vrea sa stiu daca mai pot optimiza cumva urmatorul cod:

Cod:

#include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 1000000000
long long i,j,n,i1,i2,m=2,i22,i11;
bool a[MAXSIZE];

int main()
{
    scanf("%i",&n);
    for(i=6;i<n;i+=6)
    {
        i1=i-1;
        i2=i+1;
        if(!a[i1])
        {
            m++;
            i11=i1*6;
            for(j=i11+i1;j<=n;j+=i11)
                a[j]=1;
            for(j=i1*i1;j<=n;j+=i11)
                a[j]=1;}
        if(!a[i2])
        {
            m++;
            i22=i2*6;
            for(j=i22+i2;j<=n;j+=i22)
                a[j]=1;
    }
    }
    printf("%i",m);
    return 0;
}

Nu stiu daca s-a mai folosit aceasta metoda de generare a numerelor prime. Genereaza toate numerele prime pana la 10.000.000 sub 0.4s. Am vazut alte programe de generare optimizate cu operati pe biti, eu nu prea stiu sa lucrez pe biti si as vrea sa stiu daca se poate optimiza si programelul meu pe biti si cum :D

EDIT:

Ideea folosita este ca orice numar prim este de forma 6k+1 sau 6k-1(numerele mai mari de 5).iar pentru multiplii,am folosit urmatoarea metoda:
daca scriem numerele sub forma
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
37 38 39 40 41 42
43 44 45 46 47 48
49 50 51 52 53 54
55 56 57 58 59 60
61 62 63 64 65 66
67 68 69 70 71 72
73 74 75 76 77 78
79 80 81 82 83 84
85 86 87 88 89 90
91 92 93 94 95 96
97 98 99 100 101 102
103 104 105 106 107 108
109 110 111 112 113 114
115 116 117 118 119 120
121 122 123 124 125 126
127 128 129 130 131 132
133 134 ...
toate numerele prime sunt pe doua coloane(1 si 5) si daca numeri pe coloana pe care se afla numarul n exact n linii in jos gasesti un multiplu de-al lui, asa am marcat toti multipli, o problema a fost cu coloana 5 deoarece daca inmulteam doua numere de pe coloana 5 rezultatul era pe coloana 1

Am editat si codul... e putin mai optimizat :)

Titlul: RÄƒspuns: numere prime
Scris de: Buleandra Cristian din Ianuarie 14, 2013, 02:22:33

Pai nu mi se pare o metoda buna (nici nu inteleg exact ce faci) insa complexitatea algoritmului tau este aceeasi ca la ciurul clasic ~O(n log log n) insa ai mult mai multe operatii (si majoritatea din ele foarte costisitoare) ca modulo, impartire. Ai trimis problema pe evaluatorul de la Ciur (http://infoarena.ro/problema/ciur)? Uita-te ce timpi au ceilalti cu surse de cateva linii, nu cred ca merge acest algoritm mai bine ca cel banal de ciur :).

Cat despre optimizari, nu am stat sa ma uit pe cod, dar poti sa scoti if(j!=i)...

Titlul: RÄƒspuns: numere prime
Scris de: Prehari Romica din Ianuarie 14, 2013, 11:13:31

Am mai facut cateva optimizari si am trimis-o pe evaluatorul de la ciur si timpul a fost sub 20ms, 20ms pentru numere mai mari. M-am uitat la testele de la alti si am vazut ca timpul era intre 40-50ms pentru testele mari. Am gasit un test care avea sub 8ms dar nu am nici o idee cum face, mai ales ca face cu operatii pe biti, chiar si memoria folosita era putina...

Titlul: RÄƒspuns: numere prime
Scris de: Prehari Romica din Februarie 25, 2013, 21:46:07

Am mai optimizat inca putin codul meu. Ce mi se pare ciudat este faptul ca algoritmul meu tot nu este destul de rapid pe numere mici, insa pe numere mari intrece Ciurul lui Eratostene optimizat pe biti, de exemplu la mine pe laptop pentru n=40000000 imi afiseaza putin sub 1s iar ciurul optimizat pe biti putin peste 1s. Imi poate explica cineva de ce?
Acesta ii codul:

Cod:

#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 100000001
#define S 6
#define U 1

long long i,j,j2,i1,i2,i22,i11;
long m=2,n,p;
bool a[MAXSIZE];

int main()
{
    //freopen("ciur.in","r",stdin);
    //freopen("ciur.out","w",stdout);
    scanf("%li",&n);
    p=n/7;
    for(i= S ; i <=p ; i += S)
    {
        i1 = i - U;
        i2 = i + U;
        if(! a [ i1 ])
        {
            m++;
            i11 = i1*S;
            for( j =i11+i1, j2 = i1 * i1 ; j<= n; j += i11, j2 += i11 )
                {
                    a[j]|=1;
                    if( j2 <= n )
                        {
                        a[j2]|=1;
                        }}
        }
        if(! a [ i2 ])
        {
            m++;
            i22 = i2*S;
            for(j =i2*i2 ; j <= n ; j += i22)
                {
                a[j]|=1;
            }}
        }
     for(;i<n;i+=6)
       {
           m+=!a[i+1]+!a[i-1];
       }
     printf("%ld",m);
     return 0;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Prehari Romica din Ianuarie 12, 2013, 14:01:37