В вашей функции prime есть четыре возможных пути кода, один из которых не возвращает ничего. Это то, на что жалуется сообщение об ошибке. Вам необходимо заменить:
prime (a, b-1) ;
с:
return prime (a, b-1) ;
в случае else if (b>1).
Сказав это, на самом деле это не очень хороший способ вычислить, является ли число простым. Проблема в том, что каждый рекурсивный вызов выделяет кадр стека, и вы столкнетесь с серьезными проблемами переполнения стека, если попытаетесь выяснить, является ли 99 999 999 простым числом?
Рекурсия — очень хороший инструмент для решения определенного подмножества задач, но вы должны знать о глубине стека. Что касается более эффективных решений, существует множество тестов, которые вы можете выполнить, чтобы определить, что число не простое, а затем проверить остальные только методом грубой силы.
Одна вещь, о которой вы должны знать, это сначала проверить делимость на меньшие числа, так как это уменьшит область поиска быстрее. И не используйте деление там, где подойдет умножение, умножение обычно быстрее (хотя и не всегда).
И некоторые, возможно, хитрые трюки в духе:
- каждое число, кроме 2, оканчивающееся на 2, 4, 6, 8 или 0, не является простым.
- каждое число, кроме 5, оканчивающееся на 5, не является простым. Одни только эти два правила сократят пространство поиска на 60%. Предполагая, что вы получили свой тестовый номер в виде строки, проверить последнюю цифру этой строки несложно даже до преобразования в целочисленный тип.
Есть несколько более сложных правил для проверки делимости. Если вы возьмете число, кратное 9, и просуммируете все цифры, чтобы получить новое число, затем сделаете это снова с этим числом, а затем продолжите, пока не получите одну цифру, вы обнаружите, что это всегда 9.
Это даст вам еще 10% сокращения пространства для поиска, хотя и с более затратной по времени проверкой. Имейте в виду, что эти проверки выгодны только для действительно больших чисел. Преимущества не так велики, скажем, для 32-битных целых чисел, поскольку там предварительно вычисленное растровое изображение было бы намного эффективнее (см. ниже).
Для упрощения начала я бы использовал следующее итеративное решение:
public static boolean prime (int num) {
int t = 2;
while (t * t <= num) {
if ((num % t) == 0) {
return false;
}
t++;
}
return true;
}
Если вам нужна реальная скорость в вашем коде, вообще не вычисляйте ее каждый раз. Вычислите его один раз, чтобы создать битовый массив (это сделает один из методов sieve) всех простых чисел в интересующем вас диапазоне, а затем просто проверьте свои значения по этому битовому массиву.
Если вам даже не нужны затраты на вычисление массива при каждом запуске вашей программы, сделайте это один раз и сохраните битовый массив в файл на диске, загружая его при запуске вашей программы.
На самом деле у меня есть список первых 100 миллионов простых чисел в файле, и мне проще и быстрее использовать grep, чтобы определить, является ли число простым, чем запускать код для его вычисления :-)
Что касается того, почему ваш алгоритм (исправленный оператором return) настаивает на том, что 7 не является простым, он будет настаивать на том, что каждое число не является простым (не проверял отрицательные числа, я почти уверен они вызовут серьезные проблемы - ваша первая проверка, вероятно, должна быть if (a < 1) ...).
Давайте посмотрим, что происходит, когда вы вызываете prime(3,3).
В первый раз он попадает в третье условие, поэтому вызывает prime(3,2).
Затем выполняется второе условие, поскольку 3 % (2-1) == 0 истинно (N % 1 всегда 0).
Поэтому он возвращает ложь. Вероятно, это можно исправить, изменив третье условие на else if (b>2), хотя я не проверял это тщательно, так как в любом случае не думаю, что рекурсивное решение - хорошая идея.
Следующий полный фрагмент кода сделает то, что вам нужно, хотя я ценю ваше любопытство и желание узнать, что вы сделали не так. Это знак того, кто действительно собирается стать хорошим резчиком кода.
public class prime
{
public static boolean isPrime (int num) {
int t = 2;
while (t * t <= num) {
if ((num % t) == 0) {
return false;
}
t++;
}
return true;
}
public static void main (String[] arg)
{
System.out.println (isPrime (7)) ;
}
}
person
paxdiablo
schedule
10.03.2010
