Грешка при деление на нула за проект Ойлер?

Опитвам се да разреша някои проблеми на Ойлер на проекта и по някаква причина следният код ми дава грешка при деление на нула, когато се опитвам да го стартирам с големи числа. Може ли някой да ми каже защо?

import java.util.Scanner;

    public class Problem3LargestPrimeFactor {
        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);

            System.out.println("Please enter the number to find the largest prime factor for.");
            long num = input.nextLong();
            int largest = 1;
            boolean isPrime = true;

            for(int i = 2; i < num; i++) {
                if(num % i == 0) {
                    for(int u = 2; u < i; u++){
                if(i % u == 0)
                    isPrime = false;
            }
            if(isPrime)
                largest = i;
            }
        }
    }
}

Сега съм наясно, че това не е най-ефективният начин за проектиране на алгоритъма, но може ли някой да ми каже какво се случва тук?


java divide-by-zero
person Community    schedule 17.12.2013    source източник
comment
...с големи числа. Звучи сякаш препълвате капацитета на int.   -  person woz    schedule 18.12.2013
comment
num е long, но i е само int. Така че, ако num е по-голямо от максималното цяло число, i++ в крайна сметка ще препълни. Предполагам, че в крайна сметка достига 0, след което num % i ще повиши грешка при деление на нула.   -  person Gareth Rees    schedule 18.12.2013
comment
Благодаря ти! Не мога да повярвам, че нещо толкова просто ми се изплъзна от ума.   -  person    schedule 18.12.2013
comment
Виждали ли сте този алгоритъм сито на Ератостен, тъй като вече знаете, че ограничението ви може да е полезно   -  person Felix Castor    schedule 18.12.2013

Отговори (2)


arrow_upward
0
arrow_downward

Препълваш int. В цикъла for(int i = 2; i < num; i++), num е дълго, а i е само int. Когато i достигне своя капацитет, той се обгръща до -2,147,483,648 и продължава да се увеличава, докато стигне до 0, в който момент получавате грешката си.

person woz    schedule 17.12.2013
comment
woz, използвам кода с числа в диапазона от long и той все още ми дава грешка при деление на нула. - person ; 18.12.2013
comment
Дори и да сте в обхвата на дълго, когато направите for(int i = 2; i < num; i++), i може да стане толкова голямо, колкото num, а i е само int. - person woz; 18.12.2013
comment
всякакви числа, по-големи от това, могат да ви дадат грешка -› Не е задължително, това ще прелее обратно до -2,147,483,648 и ще продължи до 0, при което ще се появи грешка. - person Sinkingpoint; 18.12.2013

arrow_upward
0
arrow_downward

Други отговори вече посочиха грешката ви. Нека ви дам по-добър алгоритъм за разлагане на съставно цяло число чрез пробно деление. Основната идея е просто да итерирате възможните фактори, като намалявате n всеки път, когато намерите такъв. Ето псевдокод:

function factors(n)
    f, fs := 2, {}
    while f * f <= n
        while n % f == 0
            append f to fs
            n := n / f
        f := f + 1
    if n > 1
        append n to fs
    return fs

Ако се интересувате от програмиране с прости числа, скромно препоръчвам това есе в моя блог.

person user448810    schedule 18.12.2013