Достаточно простая задача на нахождение простых чисел, приведу два исходника на Си / С++ для решение такой задачи. Используем знаменитый метод “Решето Эратосфена”.
Код на Си
long nn = 10000;
int mas[nn];
memset(mas, 0, sizeof(mas));
mas[0] = 1;
mas[1] = 1;
for (int i = 2; i < nn; i++)
if (!mas[i])
{
for (int j = i * 2; j < nn; j += i)
mas[j] = 1;
}
Код на c++
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<unsigned int> simples;
unsigned int n = 120;
for (unsigned int i = 2; i <= n; i++)
simples.insert(simples.end(), i);
for (std::vector<unsigned int>::iterator i = simples.begin(); i != simples.end(); i++)
{
int p = *i;
for (unsigned int j = 2*p; j <= n; j += p)//Каждый шаг прибавляем по p, начиная от 2p. Получается 2p, 3p, etc.
{
std::vector<unsigned int>::iterator item = std::find(simples.begin(), simples.end(), j);
if (item == simples.end()) continue;
if (j%p == 0)
simples.erase(item);
}
std::cout<<p<<std::endl;
}
return 0;
}
Помимо нахождения методом Эратосфена, существует еще способ, который базируется на утверждении что делить N не превосходит корень из делимого. Доказывать это утверждение здесь не будем, если есть желание можете посмотреть его самостоятельно. Код на С++ будет примерно такой.
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int min,max;
double t;
cin>>min;
cin>>max;
for(;min<max;min++)
{
bool isPrime = true;
t=ceil(sqrt((double)min));
for(int j=2;j<=t && isPrime;j++)
{
if(min % j ==0)
isPrime=false;
}
if(isPrime)
cout<<min<<" ";
}
return 0;
}
Оставить комментарий