•stef2n
|
|
« : Februarie 20, 2009, 02:08:04 » |
|
Comentarii la articolul Ciurul lui Eratostene
|
|
|
Memorat
|
Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
|
|
|
•pasarila
Strain
Karma: 0
Deconectat
Mesaje: 7
|
|
« Răspunde #1 : Martie 05, 2009, 15:19:41 » |
|
Buna ziua ! Sunt incepator si am tendinta sa ma "scarpin" cam ciudat, adica ma incurc cu variabile inutile uneori. Aveti idei de optimizare a urmatorului cod ? program ciurul_lui_Eratostene; var v1,v2:array[2..1000000] of longint; nr,i,j:longint; f:text; begin assign(f,'ciur.in'); reset(f); readln(f,nr); close(f); for i:=2 to nr do v1[i]:=i; for i:=2 to nr do begin if(v2[i]=0) then begin for j:=2 to nr do begin v2[i*j]:=1; end; end; end; end.
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #2 : Martie 05, 2009, 15:25:46 » |
|
Bineinteles ai incercat sa citesti articolul la care face referire linkul din post-ul lui Stefan? Daca faptul ca este scris in Java este un impediment, incearca sa te uiti peste problema "ciur" din arhiva educationala si sa cauti o sursa de pascal trimisa la aceasta problema.
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #3 : Martie 05, 2009, 15:30:28 » |
|
Vezi incearca asa: program ciurul_lui_Eratostene; var v1,v2:array[2..1000000] of longint; nr,i,j:longint; f:text; begin assign(f,'ciur.in'); reset(f); readln(f,nr); close(f); i := 4; while (i <= nr) do begin Prim[i] = false; i := i + 2; end i := 3; while (i * i <= nr) do begin if (Prim[i] == true) then begin j = i * i; while (j <= nr) do begin Prim[j] = false; j := j + i; end end end end. Sper ca n-am gresit nimic. Explicatia ar veni in felul urmator: Setezi la inceput pt numerele pare ca nu sunt prime, iar apoi pt fiecare nr impar, daca e prim, atunci incepi de la i * i, si cresti din i in i pana la nr. De ce de la i * i ? Pentru ca cele pana la i * i sunt de forma C * i, unde C este < i, C continand un numar prim. Sper ca ai inteles .
|
|
|
Memorat
|
|
|
|
•pasarila
Strain
Karma: 0
Deconectat
Mesaje: 7
|
|
« Răspunde #4 : Martie 06, 2009, 23:18:25 » |
|
am prins ideea. multam fain, amandurora !
|
|
|
Memorat
|
|
|
|
•truenight
Strain
Karma: 4
Deconectat
Mesaje: 23
|
|
« Răspunde #5 : Aprilie 22, 2011, 18:41:47 » |
|
Mie, pentru codul de mai jos in C, imi da ca 21, 25 si multe altele sunt numere prime. Am verificat de 2 ori, nu observ nimic diferit intre codul meu si cel final din articol (mai putin N-ul, eu m-am dus pana la 2000000000). Multumesc! #include <stdio.h> #include <stdbool.h>
#define N 100000000/8 + 1
static bool ciur[N];
int main(void) {
long i, j, nr = 1;
for(i = 1; ((i * i) << 1) + (i << 1) < N; ++i) if(!(ciur[i >> 3] & (1 << (i & 7)))) for(j = ((i * i) << 1) + (i << 1); (j << 1) + 1 < N; j += (i << 1) + 1) ciur[j >> 3] |= (1 << (j & 7));
for(i = 1; 2 * i + 1 < N; ++i) if(!(ciur[i >> 3] & (i << (i & 7)))) { ++nr; printf("%ld\n", 2 * i + 1); } printf("%ld\n\n", nr);
return 0; }
|
|
|
Memorat
|
|
|
|
•bodyionita
Strain
Karma: -2
Deconectat
Mesaje: 6
|
|
« Răspunde #6 : Decembrie 24, 2011, 10:23:48 » |
|
nu prea imi dau seama ce e gresit la tine... k am avut si eu aceeasi problema dar gresisem la incrementarea "j"-ului in For...
|
|
|
Memorat
|
|
|
|
•stelyan
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #7 : Iulie 03, 2012, 11:08:08 » |
|
ce inseamna << din for , eu stiu ca se foloseste la cin in c++, dar aici nu inteleg de ce e folosit
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #8 : Iulie 03, 2012, 11:21:49 » |
|
Este operator de shift-are pe biti . a << b este echivalent cu a * (2 ^ b) , unde ^ simbolizeaza ridicarea la putere .
|
|
|
Memorat
|
|
|
|
•romyk
Strain
Karma: 5
Deconectat
Mesaje: 40
|
|
« Răspunde #9 : Ianuarie 12, 2013, 13:08:44 » |
|
Nu ma prea pricep sa lucrez cu operati pe biti si as vrea sa stiu daca se poate optimiza codul: #include <stdio.h> #include <stdbool.h> long long i,j,k,n,m=3; bool a[1000000000]; int main() { scanf("%i",&n); // printf("2 3 5 "); for(i=7;i<=n;i+=2) if(i%3!=0) {if(i%5!=0&&a!=1) { a=1; // printf("%i ",i);
for(j=i;j<=n;j+=i*6) if(j!=i) a[j]=1;
if(i%6==5&&i<n/i) for(j=i*i;j<=n;j+=i*6) a[j]=1; } } return 0; }
am folosit o metoda asemanatoare cu cea a ciurului doar ca in alt mod de parcurgere...am facut la scoala un algoritm de generare a numerelor prime si scriind multe numere pe o foaie in coloane de 6, am obsevat ca doar pe doua coloane sunt numerele prime si ca daca numeri de la un oricare numar prim n exact n lini in jos gasesti un divizor al lui...
|
|
|
Memorat
|
|
|
|
|