Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 5.06.2014 | нет комментариев

На Прогре теснее не раз упоминали об этих Диво-числах.

Безусловно перечислять все я не буду, довольно легко заглянуть сюда.Теснее достаточно огромный период времени я отслеживаю за становлением темы примитивных чисел. И мне все огромнее хочется называть эти числа не примитивными, а феноменальными. И это не легко мое желание. Довольно припомнить высказывания эпохальных людей: «Простота — это то, что сложнее каждого на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё феноменальное легко, и всё примитивное феноменально.» Йозеф Геббельс.Хочется подметить, что примитивные числа занимают вдалеке не последнее место в криптографии.Существует уйма алгорифмов нахождения примитивных чисел. Но описать их последовательность аналитически, обнаружить обоснованность, еще никому не получалось. Давайте же посмотрим на числа и поищем среди них примитивные. Для определения всякого простого числа необходимо испробовать поделить это число на числа лежащие в диапазоне от 1 до проверяемого на простоту числа. С числами до 100 задач не появляется и дозволено подсознательно сказать является ли число простым, испробуйте! Но как быть дальше? Первое что приходит в голову это калькулятор, а отменнее компьютер. Однозначно необходима программа!Существующие способы на 1-й взор кажутся массивными и не прозрачными, трудными. И это ясно, чай это лучшее что имеется на сегодня, они оптимизированы по вероятности на максимум, прогнаны через сотни не худших голов планеты. Разбираться в готовом коде не хотелось. Для большей глубины понимания задачи, хотелось пройти путь самосильно, как первопроходец. И я решил изобрести свой велосипед и написал немножко на Java. Я знал, что некоторая реализация теснее имеется в исходниках JDK, но не стал с ней знакомится.

Пишем алгорифм поиска примитивных чисел

Так я начал. Хочу сказать сразу, что я не гнался за супер эффективность кода и о параллельности потоков не думал, мне хотелось чего-то простого пускай и не самого стремительного. Позже 2-х часов прокручивания разных схем, мне показалось, что это вдалеке не легкая задача. В один момент я даже подумал, что мне не хватает определенных навыков и познаний. Все мои попытки сводились к перебору чисел и проверки на делимость всякого числа на числа лежащие в соответственном диапазоне. При этом я пытался считать на сколько чисел мое данное число разделилось на цело, а на сколько дробно, потом сопоставлял их с присутствующим числом элементов в диапазоне. «Это число не делится ни на одно другое помимо себя и единицы»-вертелось у меня в голове. Все время я пытался сосчитать элементы на которые не делится нынешнее число. Что не приводило к надобному итогу. Мне пришлось отложить задачу. Позднее, одним вечером, разговаривая со своей женой я понял свою грубейшую ошибку. Все дело было в неправильном подходе к решению. «Легко сделай проверку на число делителей, у простого числа их неизменно будет только два и не огромнее» — подсказала мне любимая. Подлинно у всякого иного из числа из естественных их будет огромнее. В тот же вечер был написан код.

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);
	}

}

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB