Реализации алгоритмов/Перебор делителей: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
|||
Строка 32: | Строка 32: | ||
} |
} |
||
</source> |
</source> |
||
== Поиск на javascript == |
|||
<source lang="javascript"> |
|||
nextPrime: |
|||
for(var i=2; i<1000; i++) { |
|||
for(var j=2; j<i; j++) { |
|||
if ( i % j == 0) continue nextPrime; |
|||
} |
|||
alert(i); // простое |
|||
} |
|||
</source> |
|||
[[Категория:Программирование]] |
[[Категория:Программирование]] |
Версия от 14:34, 26 сентября 2013
Реализация тестирования простоты на С++
bool is_prime(int n) {
if (n <= 1)
return false;
if (n == 2)
return true;
if (n%2==0)
return false;
for (int j = 3; j * j <= n; j+=2)
if (n % j == 0) return false;
return true;
}
Нахождение всех простых до заданного N на С++
Для этого воспользуемся тестированием на простоту, но не будем перебирать все делители до корня. Для упрощения будем проверять на делимость только простыми. Для этого заведем вектор целых чисел 'prime'.
const int N = 1000*1000;
std::vector<int> prime(1, 2);
for (int i = 3; i < N; ++i){
int was = false;
for (int j = 0; j < prime.size(); ++j)
if (prime[j]*prime[j] > i)
break;
else if (i % prime[j] == 0){
was = true;
break;
}
if (!was) prime.push_back(i);
}
Поиск на javascript
nextPrime:
for(var i=2; i<1000; i++) {
for(var j=2; j<i; j++) {
if ( i % j == 0) continue nextPrime;
}
alert(i); // простое
}