如何检查一个10位数是否为素数？
如何检查一个10位数是否为素数？
提问于 2018-12-01 09:11:29
我知道赛斯的算法，直到现在我还在用它来获得10亿的素数。
但是现在我需要知道一个10位数是否是素数，而筛子的算法不能在时限内计算。
我搜索了很多，并得到了Fermat的质数测试，但是它没有成功，因为有些部分我无法理解，而另一部分则告诉我，它只告诉我们它是否可能是素数，或者不是通过某些迭代。
我想知道如何测试一个这么大的数字是否是素数，在1秒左右？对此，最有效的解决方案/算法是什么？
编辑，，我也在为筛子算法添加我的代码。
public class Random18 {
public static int sieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
boolean primes[] = new boolean[n+1];
Arrays.fill(primes,true); // assume all integers are prime.
primes[0]=primes[1]=false; // we know 0 and 1 are not prime.
for (int i=2;i<primes.length;i++) {
//if the number is prime,
//then go through all its multiples and make their values false.
if(primes[i]) {
for (int j=2;i*j<primes.length;j++) {
primes[i*j]=false;
}
}
}
if(primes[n]==true)
return 1;
else
return 0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter");
int p = scanner.nextInt();
long t1 = System.currentTimeMillis();
int k = sieveOfEratosthenes(p);
long t2 = System.currentTimeMillis();
if(k==1)
System.out.println("yes");
else
System.out.println("no");
System.out.println("took "+(t2-t1)+" millis");
scanner.close();
}
}输出像这样的大数字： 999999937 是 用了24363个磨坊
Stack Overflow用户
发布于 2018-12-01 09:27:04
您可以检查它是否是素数：
public class Prime {
public static void main(String[] args) {
int num = 10;
boolean flag = false;
for(int i = 2, max = num/2; i <= max; ++i)
{
// condition for nonprime number
if(num % i == 0)
{
flag = true;
break;
}
}
if (!flag)
System.out.println(num + " is a prime number.");
else
System.out.println(num + " is not a prime number.");
}}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53569304
复制相关文章
相似问题
腾讯云开发者
