c++ - 检查数字是否既不是素数也不是单个素数的幂的更好算法

Question

我有以下程序，其中 t 可以取 1 到 100000 之间的值，n 可以取 1 到 10^9 之间的值。

#define MAX 10000000

using namespace std;

unordered_set<long long int> s;

bool morethanone(long long int n)
{
    long long int check=0;
    for(unordered_set<long long int>::iterator it=s.begin();it!=s.end();it++)
    {
        if(n%(*it)==0)
            check++;
        if(check>1)
            return false;
    }
    return true;
}

bool isprime(long long int n)
{
    if(n%2==0)
        return false;
    for(long long int i=3;i<=sqrt(n);i+=2)
        if(n%i==0)
            return false;
    return true;
}

int main() 
{
s.insert(2);
s.insert(3);
for(long long int i=4;i<=MAX;i++)
{
        if(isprime(i))
            s.insert(i);
}

long long int t,n;
scanf("%lld",&t);
for(long long int test=0;test<t;test++)
{
    scanf("%lld",&n);
    if(n==1||s.find(n)!=s.end())
        cout<<"Santa\n";
    else if(morethanone(n))
        cout<<"Santa\n";
    else
        cout<<"Banta\n";
}

return 0;
}

基本上，程序会生成 10^9 之前的素数，如果给定的数字是素数或单个素数的幂或 1，则打印“Santa”。

以上程序适用于 MAX=10^6，但对于超过该值的任何值都显示“因超时而终止”。

Answer 1

你想确定 n 是否可以写成 p^k 用 p 素数和 k > 0 积分。

Henri Cohen 在他的计算代数数论类(class)一书中的算法 1.7.5 中描述了一个答案。他利用费马小定理和 Miller-Rabin 素性测试仪发现的 n 复合性的见证。 Cohen 证明如果 a 是 n 的复合性的见证，在 Miller-Rabin 检验的意义上，则 gcd(aⁿ - a, n) 是 n 的非平凡约数(即介于 1 和n)。

我在 将这个想法简化为 Python 代码http://ideone.com/cNzQYr并在 my blog 给出更完整的解释.这是来自 ideone.com 的有趣代码，因为没有它 Stack Overflow 不允许我发帖；去那里看看剩下的:

# returns p,k such that n=p**k, or 0,0
# assumes n is an integer greater than 1
def primePower(n):
    def checkP(n, p):
        k = 0
        while n > 1 and n % p == 0:
            n, k = n / p, k + 1
        if n == 1: return p, k
        else: return 0, 0
    if n % 2 == 0: return checkP(n, 2)
    q = n
    while True:
        a = findWitness(q)
        if a == 0: return checkP(n, q)
        d = gcd(pow(a,q,n)-a, q)
        if d == 1 or d == q: return 0, 0
        q = d