主数生成算法 [英] Prime number generation algorithm

问题描述

请查看以下内容，看看是否可以建议。

Please look at the following and see if you could advise.

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个质数的部分完成公式

The partially completed formula for calculating the nth prime

第n个素数，但所有的素因子也是如此

The nth prime is spat out but so is all of its prime factors

如何筛选列表，只找到素数。

How to sieve through the list and find only primes.

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

OK我改变了方法 - 我将尝试实现
筛选今晚 - 我现在写信息测试，但
这里是我的新实现对于一些素数。

OK I changed approaches a little - I will try implementing the sieve tonight - I am off to write Informatics test now, but here is my new implementation for the some primes.

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;
        }
    }
}

真的用了很多mem。

OK this does give primes but really uses a lot of mem. And grows slow over time as the vector gets longer.

推荐答案

消除由素数可分割的数字（2,3 ，5,7等）是一个不太糟糕的主意，当你寻找一个（小）素数的列表，但你应该使用新发现的素数，以确保该列表只包含素数（不只是2,3 ，5,7，还有那些通过：11,13,17等）

Eliminating numbers dividable by prime numbers (2,3,5,7 etc.) is a not soo bad idea when you look for a list of (small) prime numbers but you should use the newly found prime numbers too to be sure that the list contains only primes (not only 2,3,5,7 but also those passing: 11,13,17 etc.)

对于更大的素数（你不能计算解释如果数字太大，因为你需要检查几乎所有的数字（说每个4-5无论如何）从1到数字检查），通常的做法是取一个随机大数字，并检查它是否通过 Fermats Small Theorem with say 3,5,7 and 11（IIRC the probability for it it is a non prime if it pass with just

For bigger primes (you just can't calculate the way explained if the numbers are too big as you need to check almost all numbers (say each 4-5 anyhow) from 1 to the number to check), the usual approach is to take a random big number and check if it passes Fermats Small Theorem with say 3,5,7 and 11 (IIRC the probability for it to be a non prime if it passes with just 3,5,7 and 11 is really improbable).

查看 Fermats原始性测试更多的手解释。

这篇关于主数生成算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！