Posts tagged algoritm numere prime

Ciurul lui Atkin – Algoritm pentru determinarea numerelor prime

Mar 6th

Posted by admin in Algoritmi

1 comment

In acest articol veti gasi problema, iar mai jos este explicatia si rezolvarea problemei folosind Ciurul lui Atkin.

Enuntul Problemei

Spunem ca un numar natural x este prim daca si numai daca x > 1 si singurii sai divizori sunt 1 si x.

Cerinta

Dandu-se un numar natural N, sa se determine numarul numerelor prime mai mici sau egale cu N.

Date de intrare

Fisierul de intrare ciur.in contine o singura linie pe care se afla numarul N.

Date de iesire

In fisierul de iesire ciur.out se va scrie pe prima linie raspunsul cerut.

Restrictii

  • 2 ≤ N ≤ 2 000 000

Exemplu

ciur.in ciur.out
10 4

Indicatii de rezolvare

In mod normal aceasta problema se rezolva folosind Ciurul lu Eratostene. Gasiti aceasta rezolvare aici: http://tutoriale.5c.ro/2010/12/ciurul-lui-eratostene/

In cele ce urmeaza fac o prezentare a Ciurului Lui Atkin, o varianta optimizata a solutiei anterioare.

Pasii algoritmului:

- declaram un sir cu toate numerele, si consideram ca nu sunt prime (A[limita])

- cautam toate solutile x=4*i*i+j*j care satisfac conditie x mod  12 = 1 sau x mod 12 = 5, si x mai mic decat limita sirului. Se inverseaza valoarea lui A[x] (A[x] = !A[x])

- asemanator pasului anterior se face pentru x=3*i*i+j*j si x mod 12 = 7 si x mai mic decat limita (A[x] = !A[x])

- daca i>j atunci alegem toate solutile pentru x = 3*i*i-j*j care satisfac x mod 12 = 11 si x mai mic decat limita sirului. (A[x] = !A[x])

- de la 5 la radical din limita alegem toate numerele, iar din lista se taie toti multipli patratelor numerelor (n*n, 2*n*n, 3*n*n…) pana la limita sirului.

- in final A[2] si A[3] se declara adevarate.

- acum daca A[x] este adevarat inseamna ca x este prim.

 

Solutia problemei in C++

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int main()
{
 int limit;

 ifstream f("ciur.in");
 ofstream g("ciur.out");

 f>>limit;

 char A[limit];
 long int i,j,x;

 for (i=1;i<limit;i++)
 {
 A[i] = 0;
 }  

 for (i=1;i<=sqrt(limit);i++)
 for (j=1;j<=sqrt(limit);j++)
 {
    x = 4*i*i+j*j;
    if (x<limit) if ((x % 12==1) || (x % 12==5)) A[x] = !A[x];
    x = 3*i*i+j*j;
    if (x<limit) if (x % 12==7) A[x] = !A[x];     
    x = 3*i*i-j*j;     
    if (i>j) if (x<limit) if (x % 12==11) A[x] = !A[x];
 }

 for (i=5;i<=sqrt(limit);i++)
 {
     x = i*i;
     j = 1;
 while (j*x<limit)
 {
       A[j*x] =0;
       j++;
 }
 }  

 A[2] = 1;
 A[3] = 1;

 x = 0;
 for (i=2;i<limit;i++) if (A[i]) x++;

 g<<x;
}

 

, ,
Ciurul Lui Eratostene

Ciurul lui Eratostene – Algoritm pentru determinarea numerelor prime

Dec 30th

Posted by admin in Algoritmi

2 comments

În matematică, ciurul lui Eratostene este un algoritm simplu şi vechi de descoperire a tuturor numerelor prime până la un întreg specificat. Este predecesorul algoritmului modern ciurul lui Atkin, un algoritm mai rapid dar mai complex (il gasesti aici: http://tutoriale.5c.ro/2011/03/ciurcul-lui-atkin-algoritm-pentru-determinarea-numerelor-prime/). A fost creat de Eratostene, un matematician din Grecia antică.

Algoritm

  1. Se scrie o listă a numerelor de la 2 la cel mai mare număr ce urmează a fi testat pentru primalitate. Numim această listă lista A. (Lista de pătrate din partea stângă a imaginii.)
  2. Se trece numărul 2, primul număr prim găsit, într-o altă listă, cea a numerelor prime găsite. Numim această listă lista B. (Este lista din partea dreaptă a imaginii.)
  3. Se marchează 2 şi toţi multiplii lui 2 din lista A.
  4. Primul număr nemarcat din listă este un număr prim. Se trece acest număr în lista B.
  5. Se marchează acest număr şi toţi multiplii lui din lista A. Marcarea de multipli poate să înceapă de la pătratul numărului, întrucât multiplii mai mici au fost deja marcaţi în paşii anteriori.
  6. Se repetă paşii 4 şi 5 până când se epuizează toate numerele din lista A.

ENUNT

Dandu-se un numar natural N, sa se determine numarul numerelor prime mai mici sau egale cu N.

N se va citi din fisierul eratostene.in, iar numarul numerelor prime se va afisa in fisierul eratostene.out.

Rezolvare

Rezolvare in C 
#include <stdio.h>

int N, c;
char a[2000005];

int main() {
    int i, j;

	freopen("eratostene.in", "r", stdin);
	freopen("eratostene.out", "w", stdout);

	scanf("%d", &N);

    for(i=2; i<=N; i++)
		if (!a[i]) {
			++c;
			for (j = i+i; j<=N; j+=i)
				a[j]=1;
		}

    printf("%d\n", c);

    return 0;
}
Rezolvare in C++ 
#include<fstream>
#define dim 2000002
using namespace std;
char prim[dim];
long long i,j;
long long n;
long long nrprime;
ifstream f("eratostene.in");
ofstream g("eratostene.out");
int main()
{
	f>>n;
	for(i=2;i<=n;i++)
		prim[i]=1;
	for(i=2;i<=n;i++)
		if(prim[i]==1)
		{
			nrprime++;
			for(j=i+i;j<=n;j=j+i)
				prim[j]=0;
		}
		g<<nrprime;
		return 0;
}
Rezolvare in Pascal 
program ciur;
var A : array [1..2000000] of boolean;
    f : text;
    N,i,j,nr,i2,X : longint;
begin
assign(f,'eratostene.in');
reset(f);
read(f,N);
close(f);

for i := 1 to N do
A[i] := true;

for i := 2 to n do
if A[i] then for j := 2 to n div i do A[i*j] := false;

X := 0;

for i := 2 to n do
if A[i] then X := X+1;

assign(f,'eratostene.out');
rewrite(f);

write(f,X);

close(f);

end.
, ,