如何检查一个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个磨坊
回答 5
Stack Overflow用户
回答已采纳
发布于 2018-12-01 09:28:55
public static void main(String[] args) {
try (Scanner scan = new Scanner(System.in)) {
System.out.print("Enter: ");
long val = scan.nextLong();
long t1 = System.currentTimeMillis();
System.out.println(isPrime.test(val) ? "yes" : "no");
System.out.println("took " + (System.currentTimeMillis() - t1) + " millis");
}
}
static final LongPredicate isPrime = val -> {
if (val < 2)
return false;
for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
if (val % i == 0)
return false;
return true;
};输出：
Enter: 999999937
yes
took 1 millisStack 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用户
发布于 2018-12-01 09:17:53
此方法跳过所有偶数，只尝试到数字的平方根。它对你给定的号码很好。
public class Prime {
public static void main(String[] args) {
isPrime(999999937L);
}
public static boolean isPrime(long num) {
if (num > 2 && num % 2 == 0) {
System.out.println(num + " is not prime");
return false;
}
int top = (int) Math.sqrt(num) + 1;
for (int i = 3; i < top; i += 2) {
if (num % i == 0) {
System.out.println(num + " is not prime");
return false;
}
}
System.out.println(num + " is prime");
return true;
}
}我从这里那里拿来的
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53569304
复制相关文章
相似问题
腾讯云开发者
