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

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

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

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

Конечно перечислять все я не буду, достаточно просто заглянуть сюда ^[3].Уже довольно большой период времени я наблюдаю за развитием темы простых чисел. И мне все больше хочется называть эти числа не простыми, а гениальными. И это не просто мое желание. Достаточно вспомнить высказывания великих людей: «Простота — это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё гениальное просто, и всё простое гениально.» Йозеф Геббельс.Хочется отметить, что простые числа занимают далеко не последнее место в криптографии.Существует множество алгоритмов нахождения простых чисел. Но описать их последовательность аналитически, найти закономерность, еще никому не удавалось. Давайте же посмотрим на числа и поищем среди них простые. Для определения любого простого числа нужно попробовать разделить это число на числа лежащие в диапазоне от 1 до проверяемого на простоту числа. С числами до 100 проблем не возникает и можно интуитивно сказать является ли число простым, попробуйте! Но как быть дальше? Первое что приходит в голову это калькулятор, а лучше компьютер. Однозначно нужна программа!Существующие методы ^[4] на первый взгляд кажутся громоздкими и не прозрачными, сложными. И это понятно, ведь это лучшее что имеется на сегодня, они оптимизированы по возможности на максимум, прогнаны через сотни не худших голов планеты. Разбираться в готовом коде не хотелось. Для большей глубины понимания проблемы, хотелось пройти путь самостоятельно, как первопроходец. И я решил изобрести свой велосипед и написал немного на Java. Я знал, что некоторая реализация ^[5] уже имеется в исходниках 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

Источник ^[6]