Алгоритмы нахождения простых чисел на C++

Решето Сундарама

#include "stdafx.h"
#include <iostream>
using namespace std;

void Sundaram(bool massiv[], int N)
{
int i, j;
cout<<"2 ";
for (i=1; i<=N; i++)
{
massiv[i]=true;
}
i=1; j=1;
while ((2*i*j+i+j)<=N)
{
while (j<=(N-i)/(2*i+1))
{
massiv[2*i*j+i+j]=false;
j++;
}
i++;
j=i;
}
for (i=1; i<=N; i++)
{
if (massiv[i]) cout<<2*i+1<<" ";
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int N;
bool *massiv;
cout<<"Введите N"<<endl;
cin>>N;
massiv=new bool [N];
Sundaram(massiv, N/2-1);
cout<<endl;
delete [] massiv;
system("pause");
}

Результат работы програмы

Производительность 2,61 с. для 100000 последовательных положительных целых чисел

---

Решето Эратосфена на C++

Производительность 2,16 с. для 100000 последовательных положительных целых чисел

---

Решето Аткина

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

void Atkin(bool massiv[], int N)
{
int sqr_lim;
int x, y; // квадраты i и j
int i, j;
int k;

sqr_lim = (int)sqrt((long double)N);
for (i = 0; i < N; ++i)
{
massiv[i] = false;
}
massiv[2] = true;
massiv[3] = true;
x = 0;
for (i = 1; i < sqr_lim; ++i) {
x += 2 * i - 1;
y = 0;
for (j = 1; j < sqr_lim; ++j) {
y += 2 * j - 1;
k = 4 * x + y;
if ((k <= N) && (k % 12 == 1 || k % 12 == 5))
{
massiv[k] = !massiv[k];
}
// n = 3 * x2 + y2;
k -= x;
if ((k <= N) && (k % 12 == 7))
{
massiv[k] = !massiv[k];
}
// n = 3 * x2 - y2;
k -= 2 * y;
if ((i > j) && (k <= N) && (k % 12 == 11))
{
massiv[k] = !massiv[k];
}
}
}
for (i = 5; i < sqr_lim; ++i) {
if (massiv[i]) {
k = i * i;
for (j = k; j < N; j += k)
{
massiv[j] = false;
}
}
}
cout<<"2 3 5";
for (i = 6; i < N; ++i) {
if ((massiv[i]) && (i % 3 != 0) && (i % 5 != 0))
{
cout<<" "<<i;
}
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int N;
cout<<"Введите размерность массива"<<endl;
cin>>N;
bool *massiv=new bool[N];
Atkin(massiv, N);
delete [] massiv;
cout<<endl;
system("pause");
}

Результат работы програмы

Производительность 3,5 с. для 100000 последовательных положительных целых чисел

Таким образом, наиболее быстрый алгоритм — решето Эратосфена.