Алгоритм генерации простых чисел - PullRequest
Новая
       7

Алгоритм генерации простых чисел

2 голосов
/ 21 октября 2011

Пожалуйста, посмотрите на следующее и посмотрите, можете ли вы дать совет. 

cout << "2" << endl;
cout << "3" << endl;

ofstream of("Primes.txt");

unsigned long prime = 0;
unsigned long i = 1;
for (i = 1; i < 100000; i++)
{
    prime = ((i*2)+(i+1) + (i % 2));
    of << prime << endl;
}
of.close();
return 0;

Частично заполненная формула для вычисления n-го простого числа

n-е простое число выплевано, но так же, как и все его главные факторы

Как просеять через список и найти только простые числа. 

5
7
11
13
17
19
23
25
29
31
35
37
41
43
47
49
53
55
59
61
65
67
71
73
77
79
83
85
89
91
95
97
101
103

ОК. Я немного изменил подходы - попробую реализовать сита сегодня вечером - я собираюсь написать тест по информатике сейчас, но вот моя новая реализация для некоторых простых чисел. 

vector<int> Primes;

bool IsPrime(int q)
{
    for(unsigned int i = 0; i < Primes.size(); i++)
    {
        if(q % Primes[i] == 0)
            return false;
    }
    return true;
}

int main()
{
    Primes.push_back(2);
    cout << "2" << " is prime" << endl;
    for (unsigned int i = 2; i < 1000000000; i++)
    {
        if(IsPrime(i))
        {
            Primes.push_back(i);
            cout << i << " is prime" << endl;
        }
    }
}

Хорошо, это дает простые числа, но на самом деле использует много памяти. И растет медленно со временем, поскольку вектор становится длиннее.

Ответы [ 3 ]

3 голосов
/ 21 октября 2011

Исключение чисел, делимых на простые числа (2,3,5,7 и т. Д.), Является неплохой идеей, когда вы ищете список (маленьких) простых чисел, но вам также следует использовать вновь найденные простые числа, чтобы убедитесь, что в списке содержатся только простые числа (не только 2,3,5,7, но также и проходящие: 11,13,17 и т. д.)

Для больших простых чисел (вы просто не можете рассчитать объясненный способ, если числа слишком велики, так как вам нужно проверить почти все числа (скажем, каждый 4-5 в любом случае) от 1 до числа, чтобы проверить), обычный подход состоит в том, чтобы взять случайное большое число и проверить, соответствует ли оно Теореме Малого Фермаса , скажем, 3,5,7 и 11 (IIRC вероятность того, что оно будет не простым, если оно пройдет всего 3,5, 7 и 11 действительно невероятно).

Проверьте Тест на примитивность Fermats для более подробного объяснения.

0 голосов
/ 23 сентября 2013

вот самая простая логика: 

//Prime Numbers generation in C++
//Using for loops and conditional structures
#include <iostream>
using namespace std;

int main()
{
int a = 2;       //start from 2
long long int b = 1000;     //ends at 1000

for (int i = a; i <= b; i++)
{

 for (int j = 2; j <= i; j++)
 {
    if (!(i%j)&&(i!=j))    //Condition for not prime
        {
            break;
        }

    if (j==i)             //condition for Prime Numbers
        {
              cout << i << endl;

        }
 }
}
}
0 голосов
/ 11 августа 2013 
  #include<stdio.h>
int main(void)
{int x,i,l;
printf("number of enter test cases\n");
scanf("%d",&x);
if(x>10)
{
    return;
}
printf("enter the range(please do not enter 1)\n");
int mx[20];
 for(i=0;i<x*2;i=i+2)
 {
     scanf("%d%d",&mx[i],&mx[i+1]);
     if(mx[i]==1)
     {
      return;
     }
     }
       for(l=0;l<x*2;l=l+2){

     check(mx[l],mx[l+1]);
   }
  return 0;

 }
void check(int m,int n)
  { //for checking number is prime number or not
  int j,k;
 int flag;
 for(j=m;j<=n;j++)
  {   flag=0;
for(k=2;k<j;k++)
   {
       if(j%k==0)
         {
         flag++;
         }
  }
     if(flag==0)
   {
      printf("\n%d\n",j);

    }

 }
...