Всем хорошего дня!
На Хабре уже не раз упоминали об этих чудо-числах.
Конечно перечислять все я не буду, достаточно просто заглянуть сюда.Уже довольно большой период времени я наблюдаю за развитием темы простых чисел. И мне все больше хочется называть эти числа не простыми, а гениальными. И это не просто мое желание. Достаточно вспомнить высказывания великих людей: «Простота — это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё гениальное просто, и всё простое гениально.» Йозеф Геббельс.Хочется отметить, что простые числа занимают далеко не последнее место в криптографии.Существует множество алгоритмов нахождения простых чисел. Но описать их последовательность аналитически, найти закономерность, еще никому не удавалось. Давайте же посмотрим на числа и поищем среди них простые. Для определения любого простого числа нужно попробовать разделить это число на числа лежащие в диапазоне от 1 до проверяемого на простоту числа. С числами до 100 проблем не возникает и можно интуитивно сказать является ли число простым, попробуйте! Но как быть дальше? Первое что приходит в голову это калькулятор, а лучше компьютер. Однозначно нужна программа!Существующие методы на первый взгляд кажутся громоздкими и не прозрачными, сложными. И это понятно, ведь это лучшее что имеется на сегодня, они оптимизированы по возможности на максимум, прогнаны через сотни не худших голов планеты. Разбираться в готовом коде не хотелось. Для большей глубины понимания проблемы, хотелось пройти путь самостоятельно, как первопроходец. И я решил изобрести свой велосипед и написал немного на Java. Я знал, что некоторая реализация уже имеется в исходниках JDK, но не стал с ней знакомится.
Пишем алгоритм поиска простых чисел
Так я начал. Хочу сказать сразу, что я не гнался за супер производительность кода и о параллельности потоков не думал, мне хотелось чего-то простого пусть и не самого быстрого. После двух часов прокручивания различных схем, мне показалось, что это далеко не легкая задача. В один момент я даже подумал, что мне не хватает определенных навыков и знаний. Все мои попытки сводились к перебору чисел и проверки на делимость каждого числа на числа лежащие в соответственном диапазоне. При этом я пытался считать на сколько чисел мое данное число разделилось на цело, а на сколько дробно, потом сравнивал их с существующим количеством элементов в диапазоне. «Это число не делится ни на одно другое кроме себя и единицы»-крутилось у меня в голове. Все время я пытался сосчитать элементы на которые не делится текущее число. Что не приводило к нужному результату. Мне пришлось отложить задачу. Позже, одним вечером, беседуя со своей женой я осознал свою грубейшую ошибку. Все дело было в неправильном подходе к решению. «Просто сделай проверку на количество делителей, у простого числа их всегда будет только два и не больше» — подсказала мне любимая. Действительно у любого другого из числа из натуральных их будет больше. В тот же вечер был написан код.
public class Prime {
public long scan(long begin,long end) {
long divisor = 0; //количество делителей
long count = 0;
label: for(long i=begin ; i<=end; i++) { // перебираем целые числа
в указанном диапазоне
for(long j=1 ; j<=i; j++) { // перебираем делители в диапазоне
if (i % j==0) // проверяем делимость числа на цело
divisor++; // считаем делители
if (divisor>2) { // данная проверка для оптимизации,
divisor=0; // ускорила работу на том же интервале
continue label; // в 4.91 раза
}
}
if (divisor==2) { // делителей два
System.out.print(i+", "); // выводим найденное простое число
count++;
}
divisor=0;
}
return count;
}
public static void main(String[] args) {
long start, finish,count;
start = System.currentTimeMillis();
Prime A = new Prime();
count = A.scan(1,12233);
finish = System.currentTimeMillis();
System.out.print("Time = "+(finish-start)+" count = "+count);
}
}
Пока я не могу сказать на сколько алгоритм работает медленнее существующих. Конечно с увеличением количества цифр в числе, работа несколько замедляется. Возможно кому и пригодится. спасибо за внимание!
Автор: ibalykin
class Main {
public static void main(String[] args) {
int num, arg;
for(num = 2; num 0; arg++) {
}
if(arg == num) System.out.print(arg + “\t”);
}
}
}
for(num = 2; num <= 100; num++) { – эту строчку нужно вставить после int num, arg; (не знаю почему, но в комментах после отправки код урезается на эту строку. Не на одно сайте такая фигня).
А если поменять long на int, то скорость возрастёт еще втрое.