如何找到大于给定数字的最小素数?例如,给定 4,我需要 5;给定 7,我需要 11。
我想知道一些关于最佳算法的想法。我想到的一种方法是通过埃拉托色尼筛生成素数,然后在给定数之后找到素数。
来源:维基百科
Bertrand 的公设(实际上是一个定理)指出,如果 n > 3 是一个整数,那么总是存在至少一个质数 p 且 n < p < 2n - 2。一个更弱但更优雅的公式是:对于每个 n > 1 存在总是至少有一个素数 p 使得 n < p < 2n。
因此,如果给我一个数字,比如 n,我可以检查范围 (n, 2*n) [不包括 n 和 2*n 的开区间]
int GetNextPrime(int n)
{
bool isPrime = false;
for (int i = n; i < 2 * n; ++i)
{
// go with your regular prime checking routine
// as soon as you find a prime, break this for loop
}
}
已经提出了一些其他方法,我认为它们很好,但这实际上取决于您希望在现场存储或计算多少。例如,如果您正在寻找一个非常大的数字之后的下一个素数,那么使用埃拉托色尼筛法可能不是那么好,因为您需要存储的位数。
或者,您可以检查每个大于输入数的奇数 N 上的(包括)3 和 sqrt(N) 之间的所有奇数,直到找到正确的数。当然,当您发现它是复合的时,您可以停止检查。
如果您想要不同的方法,那么我建议对输入数以上的所有奇数(假设输入> 1)使用Miller-Rabin 素数测试,直到找到素数。如果您按照位于页面底部的数字列表a
来检查给定范围,则可以显着减少a
需要检查的 s 数量。当然,在使用 Miller-Rabin 进行检查之前,您可能需要检查至少几个较小的素数(例如 3、5、7、11)。
我以前做过。
唯一的补充是来自Rajendra's Answer的 Bertrand 定理。
以及来自topcoder的现成代码。
#include<iostream>
using namespace std;
/* This function calculates (ab)%c */
int modulo(int a,int b,int c){
long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
while(b > 0){
if(b%2 == 1){
x=(x*y)%c;
}
y = (y*y)%c; // squaring the base
b /= 2;
}
return x%c;
}
/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
long long x = 0,y=a%c;
while(b > 0){
if(b%2 == 1){
x = (x+y)%c;
}
y = (y*2)%c;
b /= 2;
}
return x%c;
}
/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
if(p<2){
return false;
}
if(p!=2 && p%2==0){
return false;
}
long long s=p-1;
while(s%2==0){
s/=2;
}
for(int i=0;i<iteration;i++){
long long a=rand()%(p-1)+1,temp=s;
long long mod=modulo(a,temp,p);
while(temp!=p-1 && mod!=1 && mod!=p-1){
mod=mulmod(mod,mod,p);
temp *= 2;
}
if(mod!=p-1 && temp%2==0){
return false;
}
}
return true;
}
int main(int argc, char* argv[])
{
int input = 1000;
int i = 0;
if(input%2==0)
i = input+1;
else i = input;
for(;i<2*input;i+=2) // from Rajendra's answer
if(Miller(i,20)) // 18-20 iterations are enough for most of the applications.
break;
cout<<i<<endl;
return 0;
}
我通常看到两种方法来做到这一点。
也许这也有帮助,(只需将 2 替换为给定的 Number 并将 N 替换为无限 :D ) 查找 2 和 N 之间的所有素数
我有一个大的查找表,然后搜索给定的数字,并用序列中的下一个进行响应。
如果给定数字的范围有一个已知的(合理的)上限,则效果很好。
int length = number;
bool flag = true;
for (int i = number; i <= length; i++)
{
for (int k = 2; k < length; k++)
{
if (i != k && i % k == 0)
{
flag = false;
length = length + 1;
break;
}
}
if (flag)
{
Console.WriteLine(i);
}
flag = true;
}
导入 java.util.Scanner;
公共课练习11 {
public static void main(String[] args)
{
int count=0;
Scanner scan=new Scanner(System.in);
System.out.println("enter a number:");
int a=scan.nextInt();
a: for(int i=a+1;i<a+1000;i++)// a+1000 because it will check up to
//that number to find the next prime
{
count=0;
for(int j=2;j<i;j++)
{
if(i%j==0) //this will check if a number is divisible by another
// number
{
count++;
}
else
{
}
}
if(count==0)
{
System.out.println(i);
break a;//this line will break the loop so you get only one prime
//number
}
}
}
}
private static int nextPrime(int num) {
num++;
for (int i = 2; i <num; i++) {
if(num%i == 0) {
num++;
i=2;
} else{
continue;
}
}
return num;
}