标签: primality-test

我正在努力学习口齿不清,我对素数有些困难.我需要一个功能is-prime,如果它是素数,我必须返回t,如果不是,我必须返回nil.

(prime 41) => t

(prime 35) => nil

到目前为止我有:

(defun is-prime (n d) 
  (if (= d 1) 
      (print "t") 
      (if (= (% n d) 0) 
          (print "nil") 
          (is-prime (n (- d 1) )))))

但我有2个参数,我不知道如何只使用一个.而且,它根本不起作用.谁能帮我这个？谢谢!

我有一个家庭作业问题要求我描述一个接受的非确定性图灵机的程序L = {a^n: n is prime}.我不知道如何解决这个问题.我知道吗？我使用as作为一元数字并计算它们吗？我可以忽略字符串,只测试n的主要部分吗？或者是已知的主要值,因此只有那些单元格位置接受状态,我可以像正常一样读取数据？

我该怎么办呢？

这里是...

Input: n > 3, an odd integer to be tested for primality;\nInput: k, a parameter that determines the accuracy of the test\nOutput: composite if n is composite, otherwise probably prime\nWrite n \xe2\x88\x92 1 as (2^s)\xc2\xb7d with d odd by factoring powers of 2 from n \xe2\x88\x92 1\nWitnessLoop: repeat k times:\n   pick a random integer a in the range [2, n \xe2\x88\x92 2]\n   x \xe2\x86\x90 a^d mod n\n   if x = 1 or x = n \xe2\x88\x92 1 then …

我知道Miller-Rabin素性测试是概率性的.但是我想将它用于编程任务,不会留下任何错误.

如果输入数字是64位整数(即long long在C中),我们可以假设它是非常高的概率吗？

欢迎。我正在尝试实施 MillerRabin 测试来检查给定的大数是否为素数。这是我的代码：

 public static bool MillerRabinTest(BigInteger number)
        {

            BigInteger d;
            var n = number - 1;
            var s = FindK(n, out d);

            BigInteger a = 2;
            BigInteger y = Calc(a, d, number);  //a^d mod number
            if (y != BigInteger.One && y != n)
            {
                for (var r = 1; r <= s - 1; r++)
                {
                    y = Calc(y, 2, number);
                    if (y == 1)
                        return false;  
                }

                if (y != n)
                    return false;
            }
            return true; //it is …

我对如何解决这个问题有点困惑。我需要所有素数才能返回 true。如果不返回 false——我看到我的逻辑包括 2 并且返回 0，所以它自动返回 false，因为 2 余数为 0。

  

  function isPrime(num, div = 2) {
      // BASE CASE: 
     
      if(num <= div ) return false; // IF num less than OR equal to  2 RETURN false 
      
      // IF num MOD has a remainder of zero   
         
      if(num % 2 === 0) return false  // RETURN false 
      
      return true; // RETURN true
     
      // RECURSIVE CALL:

      return isPrime(num)
    }

    console.log(isPrime(1)); //-> false
    console.log(isPrime(2)); //-> true
    console.log(isPrime(3)); //-> true
    console.log(isPrime(4)); //-> false

我是Scheme的新手.我已经尝试并使用PLT方案实现了Rabin-Miller算法的概率变体.我知道这是概率性的,但我大部分时间都得到了错误的结果.我用C实现了同样的东西,它运行良好(从未尝试过失败).我在调试时获得了预期的输出,但是当我运行时,它几乎总是以不正确的结果返回.我使用了维基百科的算法.

(define expmod( lambda(b e m)
                 ;(define result 1)
                 (define r 1)
                 (let loop()
                   (if (bitwise-and e 1)
                       (set! r (remainder (* r b) m)))
                   (set! e (arithmetic-shift e -1))
                   (set! b (remainder (* b b) m))
                   (if (> e 0)
                       (loop)))r))

(define rab_mil( lambda(n k)
                  (call/cc (lambda(breakout)
                  (define s 0)
                  (define d 0)
                  (define a 0)
                  (define n1 (- n 1))
                  (define x 0)          
                  (let loop((count 0))
                    (if (=(remainder n1 2) 0)
                        (begin
                          (set! count (+ count …

所以我对Haskell完全不熟悉,希望它不会显示太多.无论如何,我试图创建一个函数来确定一个数字是否为素数.基本思路是这样的:给定一个数字,看看它是否可被任何小于它的任何其他数字整除.如果是,则返回false.如果不是,它是素数,返回真实.到目前为止的代码(已知有效)是这样的:

divisible :: Integer -> Integer -> Bool
divisible x 2 = even x
divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))
isPrime :: Integer -> Bool
isPrime x = not (even x) && not (divisible x (x-1))

生产:

ghci> isPrime 9
False
ghci> isPrime 13
True

我想做的是稍微优化一下,因为我只需要检查小于或等于sqrt(x)的值.问题是,当我尝试实现这个时,东西变得疯狂:

isPrime x = not (even x) && not (divisible x (ceiling(sqrt(fromIntegral(x-1)))))

除了它看起来很糟糕的事实(我说我是新的),它没有给出正确的结果:

ghci> isPrime 9
False
ghci> isPrime 13
False

我想弄清楚改变了什么,因为:

ghci> ceiling(sqrt(13))
4

似乎给了我正确的号码.我知道这是一个小问题,但我很困惑......

我刚进入哈斯克尔.我正在尝试编写一个素数生成器,它会根据我给它的位数返回一个素数.我是否使用某种Eratosthenes筛子？这会是最快捷的方式吗？目前,我已经有了Miller-Rabin的素数检查器.有没有正确的方法和错误的方法来做到这一点？此外,我希望能够非常快速地生成大量数字.

防爆.生成一个32位的素数

genp 32

代码到目前为止.

import System.IO
import System.Random
import Data.List
import Control.Monad
import Control.Arrow


primesTo100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

powerMod :: (Integral a, Integral b) => a -> a -> b -> a
powerMod m _ 0 =  1
powerMod m x n | n > 0 = join (flip f (n - 1)) x `rem` m where
  f _ 0 y = y
  f a d y = g a d where
    g b i | even i    = g …

我正在尝试在 C99 中实施Miller-Rabin 素性测试，但在使其工作时遇到了一些问题。我制作了一个小的测试集来验证实现是否有效，这是我检查素数的方式

int main() {
    int foo[11] = {0, 1, 2, 3, 4, 7, 28, 73, 125, 991, 1000};
    for (int i = 0; i < 11; i++) {
        printf("%s; ", isprime(foo[i], 5000) ? "Yes" : "No");
    }
    return 0;
}

从列出的数字，预期的输出将是

不; 不; 是的; 是的; 不; 是的; 不; 是的; 不; 是的; 不;

但是，作为实施，我得到的输出如下：

不; 不; 是的; 是的; 不; 是的; 不; 不; 不; 不; 不;

这是我编写算法的方式

int randint (int low, int up){
    return rand() % (++up …