Решето Эратосфена

Постановка задания: Найти все простые числа от 1 до n

Алгоритм выглядит так:
1. Перебираем все целые числа до определенного числа n;
2. Переменная p равна первому простому числу;
3. Зачеркнуть числа равные, кратные p до числа n;
4. Найти первое число в списке большее чем p и присвоить значение переменной p;
5. Повторить шаг 3 и 4 пока не останется чисел.

Решение в виде скрипта (введите число):

Исходный код решения:

<script language=javascript> 
 function sieve()
 { 
 
var arr = [];
var arr2 = [];
var n = eval( document.forms.figure.n.value);
for (var i = 2; i < n; i++) {
 arr[i] = true
}

//шаг 2
var p = 2;

do {
 //шаг 3
 for (i = 2 * p; i < n; i += p) {
 arr[i] = false;
 }

 // шаг 4
 for (i = p + 1; i < n; i++) {
 if (arr[i]) break;
 }

 p = i;
} while (p * p < n); // шаг 5
str="";
var j=0; //заполняем новый массив простыми числами и выводим его на экран
for (i = 0; i < arr.length; i++) {
 if (arr[i]) {
 arr2[j]=i;
 j++;
 str+=i;
 str+=" ";
 }
}
 }
 </script>

Оценка - 1.0 (8)

2015-07-02 • Просмотров [ 3877 ]