Imprimă pagina - Ciurul lui Eratostene

Titlul: Ciurul lui Eratostene
Scris de: Stefan Istrate din Februarie 20, 2009, 02:08:04

Comentarii la articolul Ciurul lui Eratostene (http://infoarena.ro/ciurul-lui-eratostene)

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Porumbel Valentin din 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.

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Sima Cotizo din 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" (http://infoarena.ro/problema/ciur) din arhiva educationala (http://infoarena.ro/arhiva-educationala) si sa cauti o sursa de pascal trimisa la aceasta problema. :thumbup:

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Pripoae Teodor Anton din 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 :).

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Porumbel Valentin din Martie 06, 2009, 23:18:25

am prins ideea. multam fain, amandurora !

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: truenight din 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;
}

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Ionita Bogdan Constantin din 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...

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: ady xetney din 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

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Boaca Cosmin din 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 .

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Prehari Romica din 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...

infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: Stefan Istrate din Februarie 20, 2009, 02:08:04