我在Haskell中实现了Miller Rabin测试.我试图严格遵循例如在Miller Rabin测试的维基百科条目中给出的伪代码.现在我在网上发现,对于某些证人的选择,测试是确定性的,直到某些给定的界限.我对2 ^ 64以下的素数很感兴趣,所以我在这篇文章中找到了足够的界限 我需要哪些证人才能进行Rabin-Miller测试,最多可达10？.但是,代码似乎适用于我测试过的大多数小素数,但是对于一些较大的素数而言却失败了.例如,我尝试了十位数的素数5915587277,测试返回false.我认为我的实施是正确的,但希望有人可以发现我犯了错误并且误解了MR测试.在此先感谢您的帮助.此外,抱歉看起来凌乱的代码.
isPrime :: Int -> Bool
isPrime n = millerRabinTest n (factorizeN (n-1))
{- factorizeN finds a number s and odd number d such that n -1 = (2^s)d by
succesively dividing n by two if it is even. -}
factorizeN :: Int -> (Int, Int)
factorizeN n = fN n 0
where
fN n s | even n = fN (n `div` 2) (s + 1)
| otherwise = (n,s)
{- this is …我有以下代码,它确定一个数字是否为素数:
public static boolean isPrime(int n){
boolean answer = (n>1)? true: false;
for(int i = 2; i*i <= n; ++i)
{
System.out.printf("%d\n", i);
if(n%i == 0)
{
answer = false;
break;
}
}
return answer;
}
如何确定此函数的大O时间复杂度？在这种情况下,输入的大小是多少？
我已经读了一本竞争性编程书籍一个月了。这本书是由我国（孟加拉国）的世界决赛入围者之一撰写的。需要注意的是，这本书是用我们的母语（孟加拉语）写的，在世界范围内并不那么流行。由于内容是孟加拉语，我无法在这里引用。这就是为什么我首先感到抱歉。
在那本书的数论章节中，给出了许多测试素性的算法。他展示的最佳方案是 O(nloglogn) 中的“埃拉托斯特尼筛法”。但他写了一行。我正在翻译它。“有一种更有效的方法可以在 O(logn) 中测试素数。你自己想一下。如果你没有完成，只需谷歌一下！！”
我用谷歌搜索了一下，但没有找到满意的东西。
真的有可能在 O(logn) 中测试一个数的素数吗？如果可能的话，那么可以得出的结论是在什么范围内？
我知道这个问题之前已经被回答过，但我不太明白对该问题的解释。
我在 HackerRank 上做了 30 天的代码，其中一个练习是检查一个数字是否是素数。不幸的是，我自己无法做到这一点，所以我在多次尝试后检查了给定的解决方案。即使在查看了解决方案之后，我也无法理解其中一行：
// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrt(n); i += 2){
// n is not prime if it is evenly divisible by some 'i' in this range
if( n % i == 0 ){
isPrime = false;
}
}
为什么sqrt(n)在for循环中使用？
您好我已创建此程序以检查数字是否为素数.它有效,但出于某种原因说999是素数.我的错误在哪里 如果有人解释的话会很棒.谢谢!
这是我的计划:
number = raw_input('Enter a Number: ')
nnumber = int(number)
prime_range = range(2, nnumber)
for x in prime_range:
if nnumber % x == 0:
print 'Not a Prime Number!'
break
else:
print 'Prime Number!'
break
以下代码用于质数。我想知道为什么我们i<=n/2在循环中使用条件。
C程序：
#include <stdio.h>
int main()
{
int n, i, flag = 0;
printf("Enter a positive integer: ");
scanf("%d",&n);
for(i=2; i<=n/2; ++i)
{
// condition for nonprime number
if(n%i==0)
{
flag=1;
break;
}
}
if (flag==0)
printf("%d is a prime number.",n);
else
printf("%d is not a prime number.",n);
return 0;
}