В вашей функции 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;
}
Если вам нужна реальная скорость в вашем коде, не рассчитывайте ее каждый раз вообще. Вычислите его один раз, чтобы создать битовый массив (один из методов сита) для всех простых чисел в интересующем диапазоне, а затем просто проверьте свои значения по этому битовому массиву.
Если вам даже не нужна стоимость вычисления массива при каждом запуске вашей программы, сделайте это один раз и сохраните битовый массив в файл на диске, загружая его при запуске вашей программы.
На самом деле у меня есть список первых 100 миллионов простых чисел в файле, и мне проще и быстрее использовать grep, чтобы определить, является ли число простым, чем запустить некоторый код для его вычисления: -)
Что касается того, почему ваш алгоритм (исправленный с помощью оператора return) настаивает на том, что 7 не является простым, он будет настаивать на том, что каждое число не является простым (не проверялось с отрицательными числами, я Я уверен, что они вызовут серьезные проблемы - ваша первая проверка, вероятно, должна быть if (a < 1) ...).
Давайте рассмотрим, что происходит, когда вы звоните prime(3,3).
Впервые он достигает третьего условия, поэтому вызывает prime(3,2).
Затем выполняется условие секунда , поскольку 3 % (2-1) == 0 имеет значение true (N % 1 равно всегда 0).
Так что возвращается false. Вероятно, это можно исправить, изменив третье условие на 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)) ;
}
}