Простое число

Алгоритмы нахождения простых чисел подряд

Алгоритмы работают 1 секунду, после чего показывают результаты работы. Перед работой алгоритмов формируется массив, куда записываются найденные простые числа. Особенности каждого алгоритма описываются ниже.

Самый простой способ поиска простого числа

Перебираем каждую цифру (N) от 3 и до окончания времени (t), и делим её на все числа от 2 до N-1 (ну, явно, на единицу и на само себя любая цифра разделится нацело). Цифра 2, простое число, заносится в массив вручную перед началом работы цикла поиска.

Это самый медленный, но самый понятный способ нахождения простого числа.

Запуск

Код

	function primeSimple(){
		// основная функция
		function prime(){
			// инициализация
			var iStartTime = startTime();
			var iMaxTime = 1000;
			var iTime = 0;
			var aBase = new Array();
			var iColBase = 0;
			var bFlag = false;
			// блок переменных
			aBase[iColBase] = 2;
			iColBase++;
			var i = 3; 
			var j = 2; 
			var k = i; 
			var l = 0;			
			while ( iTime < iMaxTime ){
				if ( i % j == 0 ){
					bFlag = true;
				}else if ( i == j + 1 ){
					aBase[iColBase] = i;
					iColBase++;
					bFlag = true;
				}
				if ( bFlag ){
					j = 1;
					i++;
					bFlag = false;
				}
				j++;
				k = i;
				l++;
				iTime = endTime(iStartTime);
			}
			iTime = endTime(iStartTime);
			// вывод результата
			sAnswer = '';
			sAnswer += 'Количество простых чисел: ' + iColBase + '<br />';
			sAnswer += 'Стали делить: ' + k + '<br />';
			sAnswer += 'Число делений: ' + l + '<br />';
			sAnswer += 'Время выполнения: ' + iTime/1000 + ' сек.<br />';
			sAnswer += 'Найденные числа: <br />';
			for ( i = 0; i < iColBase; i++ ){
				sAnswer += aBase[i] + '; ';
			}
			return sAnswer;
		}
		// функция засечки времени - начало
		function startTime(){
			var time = new Date();
			time = time.getTime();
			return time;
		}
		// функция засечки времени - конец
		function endTime(startTime){
			var time = new Date();
			time = time.getTime();	
			time -= startTime;
			return time;	
		}
		return prime();
	}

Способ посложнее

Перебираем каждую цифру (N) от 3 и до окончания времени (t), и делим её на все числа от 2 до корня от N включительно. Цифра 2, простое число, заносится в массив вручную перед началом работы цикла поиска.

Этот способ побыстрее, примерно в 7,4 раза, чем первый.

Запуск

Код

	function primeSimpleAdvanced(){
		// основная функция
		function prime(){
			// инициализация
			var iStartTime = startTime();
			var iMaxTime = 1000;
			var iTime = 0;
			var aBase = new Array();
			var iColBase = 0;
			var bFlag = false;
			// блок переменных
			aBase[iColBase] = 2;
			iColBase++;
			var i = 3; 
			var j = 2; 
			var k = i; 
			var l = 0; 
			var iSquare = Math.floor(Math.sqrt(i));
			while( iTime < iMaxTime ){
				if ( i % j == 0 ){ 
					bFlag = true; 
				}else if ( j >= iSquare ){
					aBase[iColBase] = i;
					iColBase++;
					bFlag = true;
				}
				if ( bFlag ){
					j = 1;
					i++;
					iSquare = Math.floor(Math.sqrt(i));
					bFlag = false;
				}
				j++;
				k = i;
				iTime = endTime(iStartTime);
				l++;
			}
			iTime = endTime(iStartTime);
			// вывод результата
			sAnswer = '';
			sAnswer += 'Количество простых чисел: ' + iColBase + '<br />';
			sAnswer += 'Стали делить: ' + k + '<br />';
			sAnswer += 'Число делений: ' + l + '<br />';
			sAnswer += 'Время выполнения: ' + iTime/1000 + ' сек.<br />';
			sAnswer += 'Найденные числа: <br />';
			for ( i = 0; i < iColBase; i++ ){
				sAnswer += aBase[i] + '; ';
			}
			return sAnswer;
		}
		// функция засечки времени - начало
		function startTime(){
			var time = new Date();
			time = time.getTime();
			return time;
		}
		// функция засечки времени - конец
		function endTime(startTime){
			var time = new Date();
			time = time.getTime();	
			time -= startTime;
			return time;	
		}
		return prime();
	}

Способ № 3

Перебираем все цифры (N), которые оканчиваются на 1, 3, 7 или 9 (всё, что кончается на 0 или 5, явно не простое число ), и делим их на все числа от 3 до корня от N включительно. Цифры 2, 3 и 5, простые числа, заносятся в массив вручную перед началом работы цикла поиска.

Этот способ быстрее, примерно в 8,3 раза, чем первый.

Запуск

Код

	function primeMiddle(){
		// основная функция
		function prime(){
			// инициализация
			var iStartTime = startTime();
			var iMaxTime = 1000;
			var iTime = 0;
			var aBase = new Array();
			var iColBase = 0;
			var bFlag = false;
			// блок переменных
			aBase[iColBase] = 2;
			iColBase++;
			aBase[iColBase] = 3;
			iColBase++;
			aBase[iColBase] = 5;
			iColBase++;
			var i = 7; 
			var j = 3; 
			var k = i; 
			var l = 0; 
			var iShag = 0;
			var iSquare = Math.floor(Math.sqrt(i));
			while ( iTime < iMaxTime ){
				if ( i % j == 0 ){
					bFlag = true;
				}else if ( j >= iSquare ){
					aBase[iColBase] = i;
					iColBase++;
					bFlag = true;
				}
				if ( bFlag ){
					j = 2;		
					if ( iShag == 3 ){ 
						i+=4; 
						iShag = 0; 
					}else { 
						i+=2; 
						iShag++; 
					}
					iSquare = Math.floor(Math.sqrt(i));
					bFlag = false;
				}
				j++;
				k = i;
				iTime = endTime(iStartTime);
				l++;
			}
			iTime = endTime(iStartTime);
			// вывод результата
			sAnswer = '';
			sAnswer += 'Количество простых чисел: ' + iColBase + '<br />';
			sAnswer += 'Стали делить: ' + k + '<br />';
			sAnswer += 'Число делений: ' + l + '<br />';
			sAnswer += 'Время выполнения: ' + iTime/1000 + ' сек.<br />';
			sAnswer += 'Найденные числа: <br />';
			for ( i = 0; i < iColBase; i++ ){
				sAnswer += aBase[i] + '; ';
			}
			return sAnswer;
		}
		// функция засечки времени - начало
		function startTime(){
			var time = new Date();
			time = time.getTime();
			return time;
		}
		// функция засечки времени - конец
		function endTime(startTime){
			var time = new Date();
			time = time.getTime();	
			time -= startTime;
			return time;	
		}
		return prime();
	}

Способ № 4

Перебираем все цифры (N), которые оканчиваются на 1, 3, 7 или 9 (всё, что кончается на 0 или 5, явно не простое число ), и делим их на все найденные до этого времени простые числа, от 3 до корня от N включительно. Цифры 2, 3 и 5, простые числа, заносятся в массив вручную перед началом работы цикла поиска.

Этот способ быстрее, примерно в 9,1 раза, чем первый.

Запуск

Код

	function primeMiddleAdvanced(){
		// основная функция
		function prime(){
			// инициализация
			var iStartTime = startTime();
			var iMaxTime = 1000;
			var iTime = 0;
			var aBase = new Array();
			var iColBase = 0;
			var bFlag = false;
			// блок переменных
			aBase[iColBase] = 2;
			iColBase++;
			aBase[iColBase] = 3;
			iColBase++;
			aBase[iColBase] = 5;
			iColBase++;
			var i = 7; 
			var j = 1; 
			var k = i; 
			var l = 0; 
			var iShag = 0;
			var iSquare = Math.floor(Math.sqrt(i));
			while ( iTime < iMaxTime ){	
				if ( i % aBase[j] == 0 ){
					bFlag = true;
				}else if ( j >= iSquare ){
					aBase[iColBase] = i;
					iColBase++;
					bFlag = true;
				}
				if ( bFlag ){
					j = 0;
					if ( iShag == 3 ){ 
						i+=4; 
						iShag = 0; 
					}else { 
						i+=2; 
						iShag++; 
					}
					iSquare = Math.floor(Math.sqrt(i));
					bFlag = false;
				}
				j++;
				k = i;
				iTime = endTime(iStartTime);
				l++;
			}
			iTime = endTime(iStartTime);
			// вывод результата
			sAnswer = '';
			sAnswer += 'Количество простых чисел: ' + iColBase + '<br />';
			sAnswer += 'Стали делить: ' + k + '<br />';
			sAnswer += 'Число делений: ' + l + '<br />';
			sAnswer += 'Время выполнения: ' + iTime/1000 + ' сек.<br />';
			sAnswer += 'Найденные числа: <br />';
			for ( i = 0; i < iColBase; i++ ){
				sAnswer += aBase[i] + '; ';
			}
			return sAnswer;
		}
		// функция засечки времени - начало
		function startTime(){
			var time = new Date();
			time = time.getTime();
			return time;
		}
		// функция засечки времени - конец
		function endTime(startTime){
			var time = new Date();
			time = time.getTime();	
			time -= startTime;
			return time;	
		}
		return prime();
	}

Пояснения

«Количество простых чисел»: количество чисел, найденное за единицу времени. «Стали делить»: то число, которое проходило проверку в момент прекращения работы алгоритма. «Число делений»: общее количество действий типа «деление», которое делает алгоритм за единицу времени. «Время выполнения»: время работы алгоритма. Учитывает время подготовки локальных данных функцией поиска и время работы алгоритма. Время для вывода данных на экран не учитывается.

Особо внимательные могли заметить, что во время работы алгоритмов подсчитывается количество делений — одного из самых затратных для процессора операций. Так вот это количесто во всех вариантах одинаково (+/- погрешность). Это показатель того, как качество кода влияет на производительность. Процессор один, а вот найдено чисел в разных вариантах разное количество.

Алгоритмы нахождения максимального простого числа

Продолжение следует :)

Алгоритмы проверки произвольного числа на простоту

Продолжение следует :)

Списки простых чисел

Простые числа от 1 до 100 000.

Простые числа от 100 000 до 200 000.



Комментировать

Желающим сделать комментарий — ссылка!