Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Ciurul lui Eratostene  (Citit de 12292 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : 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 Deconectat

Mesaje: 7



Vezi Profilul
« 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 ?
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
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #2 : Martie 05, 2009, 15:25:46 »

Bineinteles Smile 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. Thumb up
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #3 : Martie 05, 2009, 15:30:28 »

Vezi incearca asa:

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);
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 Smile.
Memorat
pasarila
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #4 : Martie 06, 2009, 23:18:25 »

am prins ideea. multam fain, amandurora !
Memorat
truenight
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 23



Vezi Profilul
« 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!
Cod:

#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 Deconectat

Mesaje: 6



Vezi Profilul
« 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 Deconectat

Mesaje: 1



Vezi Profilul
« 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
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« 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 Deconectat

Mesaje: 40



Vezi Profilul
« 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
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines