Есть ли простой алгоритм, который может определить, является ли X простым, и не запутать простого смертного программиста?

Question

Я пытался пройти через Project Euler и заметил несколько проблем, требующих, чтобы вы определили простое число как его часть.

1. Я знаю, что могу просто разделить x на 2, 3, 4, 5, ..., квадратный корень из X и, если я доберусь до квадратного корня, я могу (безопасно) предположить, что число простое , К сожалению, это решение кажется довольно клунким.

2. Я изучил более эффективные алгоритмы определения того, является ли число простым, но быстро запутался.

Существует ли простой алгоритм, который может определить, является ли X простым, и не запутать простого смертного программиста?

Большое спасибо!

Answer 1

Для Project Euler наличие списка простых чисел действительно необходимо. Я бы предложил вести список, который вы используете для каждой проблемы.

Я думаю, что вы ищете это Сито Эратосфена .

Answer 2

Может быть, эта реализация в 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)
    }
}

Answer 3

Не оптимизировано, но это очень простая функция.

    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;
    }

Answer 4

Другой способ в 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()  

Answer 5

Мне нравится этот код 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

Конечно, если бы я вычислял партию чисел, я бы не пересчитывал кеш; Я бы сделал это один раз и сделал бы поиск в нем.

Answer 6

Алгоритм первичного тестирования 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;