Вопрос по java – для цикла поиска простых чисел

2

Я пытаюсь запустить этот код, чтобы вывести сумму всех простых чисел менее 2 миллионов. Этот цикл никогда не заканчивается. Может кто-нибудь сказать мне, что не так с кодом? Похоже, работает с меньшими числами, хотя.

public static void main(String[] args) {

        long result = 1;

        for(int i=0; i<2000000; i++) {
            if(isPrime(i)) {
                result+= i;
            }
        }
        System.out.println(result);

    }
private static boolean isPrime(long n) {
    boolean result = false;

    for(long i=2; i<(long)Math.sqrt(n); i++) {
        if(n%i == 0) {
            result = false;
            break;
        }
        else result = true;
    }
    return result;
}
пожалуйста, отправьте isPrime код Sleiman Jneidi
Я думаю, что ваш isPrime занимает все больше и больше времени. Вы можете проверить это, добавляя выходные данные отладки каждый раз, когда isPrimer возвращает true. Кроме того, результат должен начинаться с 1? Roger Lindsjö
В текущем коде есть ошибка. Если число является произведением двух простых чисел, оно будет неправильно определено как простое число. Если бы я писал код, я быi<=(long)Math.sqrt(n)+1 (потому что я не знаю, как работает округление - делает(long)Math.sqrt(25) становиться(long)4.99999 становиться4? - и я бы предпочел небольшую неэффективность неправильным результатам). Либо так, либо посмотрите, как java выполняет округление. emory

Ваш Ответ

5   ответов
5

isPrime вы только тестируете деление на 2:

private static boolean isPrime(long n) {
    boolean result = false;

    for(long i=1; i<n/2; i++) {
        if(n%2 == 0) {
            result = false;
            break;
        }
        else result = true;
    }
    return result;

}

это должно быть деление каждогоi и начиная с 2:

for(long i=2; i<n/2; i++) {
    if(n%i == 0) {
      ...

Практически в вашей текущей версии нечетное числоn будет делиться на 2 доn/2 вместо того, чтобы останавливаться намного раньше. Рассмотрим n = 21. ы делите на 2 от 1 до 10 вместо того, чтобы делить на 3 на 3-м шаге и выходите.

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

Edit: Для более быстрых результатов проверьте это сито Erathostenes метод:

public static long sumOfPrimes(int n) {

    long sum = 0;

    boolean[] sieve = new boolean[n];
    for(int i = 2; i < Math.sqrt(n); i++) {
        if(!sieve[i]) {
            for(int j = i * i; j < n; j += i) {
                sieve[j] = true;
            }
        }
    }

    for(int i = 2; i < n; i++) {
        if(!sieve[i]) {             
            sum += i;
        }
    }

    return sum;
}

Edit #2: Найдено несколько ошибок в вашей новой версии. от исправленный:

private static boolean isPrime(long n) {
    boolean result = false;

    if(n == 2 || n == 3) return true;

    for (long i = 2; i <= (long) Math.sqrt(n); i++) {
        if (n % i == 0) {
            result = false;
            break;
        } else
            result = true;
    }

    System.out.println(n + " " + result);
    return result;
}
@ nick-s: Нет, ты не имеешь. Это только исправленная версия вашего начальногоisPrime метод. Не нужно ничего менять в вашем общем алгоритме. Просто подключите его и проверьте.
@ Bohemian: Да, деление на 1. Спасибо.
Вы полностью пропустили другую серьезную ошибку ...
ребята, я внес изменения, но они все еще продолжают работать. я разместил код в оригинальном вопросе. ты видишь, что я делаю не так? nick-s
но для этого мне может понадобиться сохранить массив всех простых чисел меньше, чем «n»; чтобы избежать этого. Я думаю, что это намного дольше. nick-s
2

isPrime()

Тест должен быть:

if(n%i == 0) { ...

и вам нужно начать считать2не1потому что каждое число имеет остаток от нуля при делении на1!

Кроме того, не нужно проходить мимоMath.sqrt(n).

Вы должны изменить это на это:

private static boolean isPrime(long n) {
    long max = (long)Math.sqrt(n);
    for (long i = 2; i < max; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

К вашему сведению, с этим изменением я протестировал программу на своем ПК, и она завершилась менее чем за 1 секунду, давая результат143064094810

ура за ваш ответ nick-s
почему мне не нужно проходить мимоMath.sqrt(n)?? nick-s
Потому что вы пытаетесь найтиa * b == n а такжеMath.sqrt(n) * Math.sqrt(n) == nтак что любое число большеMath.sqrt(n) заa  вы уже попробовали на пути какb.
0

Tested and bug free Prime check function
static boolean isPrime(int n) {
    if (n == 1) return false;

    for(int i = 2; i <= n/2; i++)
        if(n % i == 0)
            return false;

    return true;
}
0

isPrime функция должна вычислить все простые числа доi (или хотя бы доsqrt(i)) каждый раз, когда он работает. Убедитесь, что ваша функция isPrime кэширует свои результаты!

0

Here is a complete program of Prime using JOptionPane, i.e. Java GUI


public class ChkPrime {
    public static void main(String[] args) throws NumberFormatException {
        String str = JOptionPane.showInputDialog(null, "Enter any number: ","Input...", 3);

        try {
            int num = Integer.parseInt(str);


            if (num == 1)
                JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is not prime.","Error!", 0);

            for(int i = 2; i <= Math.sqrt(num); i++) {
                if(num % i == 0) {
                    JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is not prime.","Error!", 0);
                    System.exit(0);
                }
            }

            JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is prime.","Yeh! Got it!", 1);
        }

        catch (NumberFormatException e) {
            JOptionPane.showMessageDialog(null, "Please input numbers...","Error!", 0);
            main(null);
        }
    }
}

Похожие вопросы