29

我一直在尝试通过 Project Euler 进行工作，并且注意到一些问题要求您确定素数作为其中的一部分。

  1. 我知道我可以将 x 除以 2, 3, 4, 5, ..., X 的平方根，如果我得到平方根，我可以（安全地）假设这个数字是素数。不幸的是，这个解决方案似乎很笨拙。

  2. 我已经研究过更好的算法来确定一个数字是否是素数，但很快就会感到困惑。

有没有一种简单的算法可以确定 X 是否为素数，并且不会让普通程序员感到困惑？

非常感谢！

4

16 回答 16

28

第一个算法非常好，在 Project Euler 中使用了很多。如果你知道你想要的最大数量，你也可以研究 Eratosthenes 的筛子。

如果您维护素数列表，您还可以改进第一个算法以仅与素数相除，直到数字的平方根。

使用这两种算法（除法和筛子），您应该能够解决问题。

编辑：固定名称，如评论中所述

于 2008-10-09T18:05:32.503 回答
20

生成小于Eratosthenes 限制的所有素数（该页面包含 20 种编程语言的变体）是最古老和最简单的解决方案。

在 Python 中：

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

例子：

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
于 2008-10-11T02:13:19.680 回答
12

我看到已经提出了 Fermat 的素性检验，但我一直在研究计算机程序的结构和解释，他们还给出了Miller-Rabin 检验（参见第 1.2.6 节，问题 1.28）作为另一种选择。我一直在成功地使用它来解决欧拉问题。

于 2008-10-09T20:17:56.917 回答
5

这是您的方法的简单优化，它不是埃拉托色尼筛法，但很容易实现：首先尝试将 X 除以 2 和 3，然后循环 j=1..sqrt(X)/6，尝试除乘以 6*j-1 和 6*j+1。这会自动跳过所有可被 2 或 3 整除的数字，从而获得相当不错的常数因子加速。

于 2008-10-09T18:25:47.670 回答
5

请记住以下事实（来自MathsChallenge.net）：

  • 除 2 以外的所有素数都是奇数。
  • 所有大于 3 的素数都可以写成 6k - 1 或 6k + 1 的形式。
  • 您不需要检查 n 的平方根

这是我用于相对较小的 n 的 C++ 函数：

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

您可能会想到自己的更多优化。

于 2009-01-25T22:50:45.940 回答
3

我推荐费马的素数检验。这是一个概率测试，但它经常是正确的。与筛子相比，它的速度非常快。

于 2008-10-09T18:22:59.503 回答
2

对于相当小的数字，最多为 sqrt(x) 的 x%n 非常快速且易于编码。

简单的改进：

仅测试 2 和奇数。

测试 2、3 和 6 + 或 - 1 的倍数（除 2 或 3 之外的所有素数都是 6 +/- 1 的倍数，因此您基本上只是跳过所有偶数和所有 3 的倍数

仅测试素数（需要计算或存储直到 sqrt(x) 的所有素数）

您可以使用 sieve 方法快速生成所有素数的列表，直到某个任意限制，但它往往会占用大量内存。您可以使用 6 的倍数技巧将内存使用量减少到每个数字的 1/3 位。

我写了一个简单的素数类（C#），它使用两个位域来表示 6+1 的倍数和 6-1 的倍数，然后进行简单的查找......如果我正在测试的数字超出了筛子的范围，然后它依靠 2、3 和 6 +/- 1 的倍数进行测试。我发现，对于我迄今为止解决的大多数欧拉问题，生成一个大筛子实际上比动态计算素数需要更多时间。KISS原则再次来袭！

我编写了一个素数类，它使用筛子预先计算较小的素数，然后依靠 2、3 和 6 的倍数 +/- 1 来测试筛子范围之外的素数。

于 2008-12-01T04:36:16.360 回答
1

对于欧拉计划来说，拥有一个素数列表真的很重要。我建议维护一个用于每个问题的列表。

我想你要找的是埃拉托色尼筛。

于 2008-10-09T18:10:20.510 回答
1

你的权利是最慢的。您可以对其进行一些优化。

研究使用模数而不是平方根。跟踪你的素数。您只需要将 7 除以 2、3 和 5，因为 6 是 2 和 3 的倍数，而 4 是 2 的倍数。

Rslite 提到了eranthenos 筛子。这是相当直截了当的。我有它家的几种语言。如果您希望我稍后发布该代码，请添加评论。

这是我的 C++ 之一。它有很大的改进空间，但与动态语言版本相比，它的速度更快。

// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>

int main(void) {
        // using unsigned short.
        // maximum value is around 65000
        const unsigned short max = 50000;
        unsigned short x[max];
        for(unsigned short i = 0; i < max; i++)
                x[i] = i + 2;

        for(unsigned short outer = 0; outer < max; outer++) {
                if( x[outer] == 0)
                        continue;
                unsigned short item = x[outer];
                for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
                        unsigned int searchvalue = item * multiplier;
                        unsigned int maxValue = max + 1;
                        for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
                                if(x[maxIndex] != 0) {
                                        maxValue = x[maxIndex];
                                        break;
                                }
                        }
                        for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
                                if( searchvalue > maxValue )
                                        break;
                                if( x[searchindex] == searchvalue ) {
                                        x[searchindex] = 0;
                                        break;
                                }
                        }
                }
        }
        for(unsigned short printindex = 0; printindex < max; printindex++) {
                if(x[printindex] != 0)
                        std::cout << x[printindex] << "\t";
        }
        return 0;
}

我一找到 Perl 和 python 代码，我就会扔掉它。它们的风格相似，只是线条较少。

于 2008-10-09T18:27:43.470 回答
1

这是 D（数字火星）中的简单素数测试：

/** 
 * to compile:
 * $ dmd -run prime_trial.d
 * to optimize:
 * $ dmd -O -inline -release prime_trial.d 
 */
module prime_trial;

import std.conv : to;  
import std.stdio : w = writeln;

/// Adapted from: http://www.devx.com/vb2themax/Tip/19051 
bool 
isprime(Integer)(in Integer number) 
{
  /* manually test 1, 2, 3 and multiples of 2 and 3 */
  if (number == 2 || number == 3)
    return true;
  else if (number < 2 || number % 2 == 0 || number % 3 == 0)
    return false;

  /* we can now avoid to consider multiples 
   * of 2 and 3. This can be done really simply 
   * by starting at 5 and incrementing by 2 and 4 
   * alternatively, that is: 
   *    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...    
   * we don't need to go higher than the square root of the number */
  for (Integer divisor = 5, increment = 2; divisor*divisor <= number; 
       divisor += increment, increment = 6 - increment) 
    if (number % divisor == 0)
      return false;

  return true;  // if we get here, the number is prime
}

/// print all prime numbers less then a given limit
void main(char[][] args) 
{
  const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
  for (uint i = 0; i < limit; ++i) 
    if (isprime(i))
      w(i);
}
于 2008-10-11T01:56:39.217 回答
1

我也在解决 Project Euler 问题，实际上刚刚完成了#3（按 id），这是对合数的最高质因数的搜索（? 中的数字是 600851475143）。

我查看了所有关于素数的信息（这里已经提到过筛技术），以及关于 wikipedia 上的整数分解的信息，并提出了一个我决定要做的蛮力试验除法算法。

因此，当我在做欧拉问题来学习 ruby​​ 时，我正在研究我的算法并偶然发现了 mathn 库，它有一个Prime 类和一个带有 prime_division方法的 Integer 类。多么酷啊。我能够通过这个红宝石片段得到问题的正确答案：

require "mathn.rb"
puts 600851475143.prime_division.last.first

此代码段将正确答案输出到控制台。当然，在我偶然发现这个小美女之前，我最终做了很多阅读和学习，我只是想我会与大家分享...

于 2009-01-23T14:36:04.730 回答
0

我喜欢这个 python 代码。

def primes(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] ==  i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    return [j for j in xrange(2, limit) if x[j] == 1]

它的一个变体可用于生成数字的因数。

def factors(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] == i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    result = []
    y = limit-1
    while x[y] != 1 :
        divisor = x[y]
        result.append(divisor)
        y /= divisor
    result.append(y)
    return result

当然，如果我分解一批数字，我不会重新计算缓存；我会做一次并在其中进行查找。

于 2009-02-18T17:41:51.127 回答
0

没有优化，但它是一个非常简单的功能。

    function isprime(number){

    if (number == 1)
        return false;

    var times = 0;

    for (var i = 1; i <= number; i++){
        if(number % i == 0){
            times ++;
        }
    }
        if (times > 2){
            return false;
        }

    return true;
    }
于 2013-04-05T10:40:04.717 回答
0

也许这个 Java 实现会有所帮助：

public class SieveOfEratosthenes {

    /**
     * Calling this method with argument 7 will return: true true false false true false true false
     * which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
     * 5 is prime, 6 is NOT prime, 7 is prime.
     * Caller may either revert the array for easier reading, count the number of primes or extract the prime values
     * by looping.
     * @param upTo Find prime numbers up to this value. Must be a positive integer.
     * @return a boolean array where index represents the integer value and value at index returns
     * if the number is NOT prime or not.
     */
    public static boolean[] isIndexNotPrime(int upTo) {
        if (upTo < 2) {
            return new boolean[0];
        }

        // 0-index array, upper limit must be upTo + 1
        final boolean[] isIndexNotPrime = new boolean[upTo + 1];

        isIndexNotPrime[0] = true; // 0 is not a prime number.
        isIndexNotPrime[1] = true; // 1 is not a prime number.

        // Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
        // Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
        // Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
        // Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
        // Repeat process until i * i > isIndexNotPrime.len.
        // Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
        // primes above 121..
        for (int i = 2; i < isIndexNotPrime.length; i++) {
            if (i * i >= isIndexNotPrime.length) {
                break;
            }
            if (isIndexNotPrime[i]) {
                continue;
            }
            int multiplier = i;
            while (i * multiplier < isIndexNotPrime.length) {
                isIndexNotPrime[i * multiplier] = true;
                multiplier++;
            }
        }

        return isIndexNotPrime;
    }

    public static void main(String[] args) {
        final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
        assert !indexNotPrime[2]; // Not (not prime)
        assert !indexNotPrime[3]; // Not (not prime)
        assert indexNotPrime[4]; // (not prime)
        assert !indexNotPrime[5]; // Not (not prime)
        assert indexNotPrime[6]; // (not prime)
        assert !indexNotPrime[7]; // Not (not prime)
    }
}
于 2018-08-13T00:00:03.277 回答
-1

AKS 主要测试算法： 

Input: Integer n > 1  


if (n is has the form ab with b > 1) then output COMPOSITE  

r := 2  
while (r < n) {  
    if (gcd(n,r) is not 1) then output COMPOSITE  
    if (r is prime greater than 2) then {  
        let q be the largest factor of r-1  
        if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break  
    }  
    r := r+1  
}  

for a = 1 to 2sqrt(r)log n {  
    if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE  
}  

output PRIME;
于 2008-10-09T18:13:27.867 回答
-2

python中的另一种方式是：

import math

def main():
    count = 1
    while True:
        isprime = True

        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break

        if isprime:
            print count


        count += 2


if __name__ == '__main__':
    main()
于 2009-02-25T21:55:25.017 回答