О простых числах. Поиск на Java

Всем хорошего дня!

На Хабре уже не раз упоминали об этих чудо-числах.

• Вот одна прекрасная их реализация

Конечно перечислять все я не буду, достаточно просто заглянуть сюда.Уже довольно большой период времени я наблюдаю за развитием темы простых чисел. И мне все больше хочется называть эти числа не простыми, а гениальными. И это не просто мое желание. Достаточно вспомнить высказывания великих людей: «Простота — это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё гениальное просто, и всё простое гениально.» Йозеф Геббельс.Хочется отметить, что простые числа занимают далеко не последнее место в криптографии.Существует множество алгоритмов нахождения простых чисел. Но описать их последовательность аналитически, найти закономерность, еще никому не удавалось. Давайте же посмотрим на числа и поищем среди них простые. Для определения любого простого числа нужно попробовать разделить это число на числа лежащие в диапазоне от 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); 	} 	 } 

Пока я не могу сказать на сколько алгоритм работает медленнее существующих. Конечно с увеличением количества цифр в числе, работа несколько замедляется. Возможно кому и пригодится. спасибо за внимание!