Как я могу улучшить этот код для Project Euler 7?

Question

Перечисляя первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы можем видеть, что шестое простое число равно 13.

Что такое 10 001-е простое число?

Мое решение:

public class Prime_Number {

    public static boolean isPrime(long n) {
        if ((n > 2 && n % 2 == 0) || (n > 3 && n % 3 == 0) || (n > 5 && n % 5 == 0) || n == 0 || n == 1) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int count = 0;
        int prime = 0;
        while (prime <= 10001) {
            if (isPrime(count) == true) {
                prime++;
                if (prime == 10001) {
                    System.out.println(count + " is a prime number" + "(" + prime + ")");
                }
            }
            count++;
        }
    }
}

Но оно не дает правильного ответа.Пожалуйста, помогите мне обновить мой код.Например, программа определяет 91 как простое число, но это не простое число.Как это улучшить?

Answer 1

Вам нужно проверить число на каждое простое число, меньшее его квадратного корня, чтобы убедиться, что оно простое.

Вы проверяете только на 2,3 и 5.

Поскольку всепростые числа не всегда выполнимы в пространстве, обычным методом является проверка на 2, а затем проверка всех нечетных чисел, начиная с 3. Это требует цикла.

рассмотрим:

boolean isPrime(long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    if (n < 9) return true;
    if (n % 3 == 0) return false;
    long max = (long)(Math.sqrt(n + 0.0)) + 1;
    for (int i = 5; i <= max; i += 6) {
        if (n % i == 0) return false;
        if (n % (i + 2) == 0) return false;
    }
    return true;
}

Answer 2

Число p является простым, если оно делится только на себя и 1. Вы проверяете только деление на 2, 3 и 5. Этого недостаточно. Проверяйте каждый номер до p / 2 или лучше до sqrt(p).

Answer 3

Следующее решение проверяет только нечетные числа, чтобы быть простыми, но оно считает 2 как простое число с начала:

public class A {

    static int N = 10001;

    private static boolean isOddPrime(long x) {

        for ( int i = 3 ; i*i <= x ; i+=2 ) {
            if ( x % i == 0 ) {
                return false;
            }               
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        long start = System.nanoTime();
        int x;
        int i = 2;      // 3 is the 2nd prime number
        for ( x = 3 ; ; x+=2 ) {
            if ( isOddPrime(x) ) {              
                if ( i == N )
                    break;
                i++;
            }
        }
        System.out.println(x);

        long stop = System.nanoTime();
        System.out.println("Time: " + (stop - start) / 1000000 + " ms");
    }
}

выход

104743
Time: 61 ms

Answer 4

Я бы прокомментировал, но я только что присоединился.

Вам не нужно проверять каждое число от 1 до квадратного корня из числа для потенциальных делителей, вы просто должны проверить все предыдущие простые числа (при условии, что вы начинаетев 1 и итерацию вверх), так как любой другой делитель, который не является простым, сам будет делиться на простое число более низкого значения.чем больше число простых чисел, тем больше проверок против не простых чисел это сохраняет.пример на C #, но это больше для демонстрации концепции.

    //store found primes here, for checking subsequent primes
    private static List<long> Primes;
    private static bool IsPrime(long number)
    {
        //no number will have a larger divisor withou some smaller divisor
        var maxPrime = Math.Sqrt(number);

        // takes the list of primes less than the square root and 
        //     checks to see if all of that list is not evenly 
        //     divisible into {number}
        var isPrime = Primes
            .TakeWhile(prime => !(prime > maxPrime))
            .All(prime => number % prime != 0);
        if (isPrime)
            Primes.Add(number);
        return isPrime;
    }

    private static long GetNthPrime(int n)
    {
        //reset primes list to prevent persistence
        Primes = new List<long> { 2, 3, 5, 7 };

        //prime in starting set
        if (Primes.Count >= n)
        {
            return Primes[n - 1];
        }

        //iterate by 6 to avoid all divisiors of 2 and 3 
        //  (also have to check i + 2 for this to work)
        //  similar to incrementing by 2 but skips every third increment 
        //  starting with the second, as that is divisible by 3
        for (long i = 11; i < long.MaxValue; i += 6)
        {
            // only check count if is prime
            if ((IsPrime(i) && Primes.Count >= n) || (IsPrime(i + 2) && Primes.Count >= n))
            {
                break;
            };
        }
        //return end of list
        return Primes[n - 1];
    }