用c++找出质数最快的算法是什么?我已经使用了sieve的算法,但我仍然希望它更快!
当前回答
#include <iostream>
using namespace std;
int set [1000000];
int main (){
for (int i=0; i<1000000; i++){
set [i] = 0;
}
int set_size= 1000;
set [set_size];
set [0] = 2;
set [1] = 3;
int Ps = 0;
int last = 2;
cout << 2 << " " << 3 << " ";
for (int n=1; n<10000; n++){
int t = 0;
Ps = (n%2)+1+(3*n);
for (int i=0; i==i; i++){
if (set [i] == 0) break;
if (Ps%set[i]==0){
t=1;
break;
}
}
if (t==0){
cout << Ps << " ";
set [last] = Ps;
last++;
}
}
//cout << last << endl;
cout << endl;
system ("pause");
return 0;
}
其他回答
你的问题是判断一个特定的数字是否是质数吗?然后你需要一个质数测试(很简单)。或者你需要一个给定数字之前的所有质数吗?在这种情况下,素筛是很好的(简单,但需要内存)。或者你需要一个数的质因数?这将需要分解(如果你真的想要最有效的方法,对于较大的数字很难)。你看到的数字有多大?16位?32位?更大的吗?
一种聪明而有效的方法是预先计算质数表,并使用位级编码将它们保存在文件中。文件被认为是一个长位向量,而位n表示整数n。如果n是素数,则其位设置为1,否则为0。查找非常快(您可以计算字节偏移量和位掩码),并且不需要在内存中加载文件。
#include <iostream>
using namespace std;
int set [1000000];
int main (){
for (int i=0; i<1000000; i++){
set [i] = 0;
}
int set_size= 1000;
set [set_size];
set [0] = 2;
set [1] = 3;
int Ps = 0;
int last = 2;
cout << 2 << " " << 3 << " ";
for (int n=1; n<10000; n++){
int t = 0;
Ps = (n%2)+1+(3*n);
for (int i=0; i==i; i++){
if (set [i] == 0) break;
if (Ps%set[i]==0){
t=1;
break;
}
}
if (t==0){
cout << Ps << " ";
set [last] = Ps;
last++;
}
}
//cout << last << endl;
cout << endl;
system ("pause");
return 0;
}
有一个100%的数学测试可以检查一个数字P是质数还是合数,叫做AKS质数测试。
概念很简单:给定一个数字P,如果(x-1)^P - (x^P-1)的所有系数都能被P整除,那么P是一个质数,否则它是一个合数。
例如,给定P = 3,会给出多项式:
(x-1)^3 - (x^3 - 1)
= x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
= 3x^2 - 3x
系数都能被3整除,所以这个数是素数。
P = 4不是质数的例子是:
(x-1)^4 - (x^4-1)
= x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
= -4x^3 + 6x^2 - 4x
这里我们可以看到系数6不能被4整除,因此它不是质数。
多项式(x-1)^P有P+1项,可以用组合法找到。因此,这个测试将在O(n)个运行时间内运行,所以我不知道这有多有用,因为你可以简单地从0到p遍历I,然后测试剩余的部分。
寻找因素的解决方案:
def divisors(integer):
result = set()
i = 2
j = integer/2
while(i <= j):
if integer % i == 0:
result.add(i)
#it dont need to
result.add(integer//i)
i += 1
j = integer//i
if len(result) > 0:
return f"not prime {sorted(result)}"
else:
return f"{integer} is prime"
—测试---- 导入的时间
start_time = time.time()
print(divisors(180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
——0.06314539909362793秒——
start_time = time.time()
print(divs(180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
——1.5997519493103027秒——
start_time = time.time()
print(divisors(1827))
print("--- %s seconds ---" % (time.time() - start_time))
——0.0秒——
start_time = time.time()
print(divisors(104729))
print("--- %s seconds ---" % (time.time() - start_time))
——0.0秒——
下面的代码:
def divs(integer):
result = set()
i = 2
j = integer / 2
loops = 0
while (i <= j):
if integer % i == 0:
print(f"loops:{loops}")
return f"{integer} is not a prime"
i += 1
j = integer // i
loops += 1
print(f"loops:{loops}")
return f"{integer} is prime"
——测试——
start_time = time.time()
print(divs(180180180180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
——0.0秒——
我总是用这种方法来计算筛子算法后面的质数。
void primelist()
{
for(int i = 4; i < pr; i += 2) mark[ i ] = false;
for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
if(mark[ i ])
for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
prime[ 0 ] = 2; ind = 1;
for(int i = 3; i < pr; i += 2)
if(mark[ i ]) ind++; printf("%d\n", ind);
}