Реализации алгоритмов/Перебор делителей: различия между версиями
Содержимое удалено Содержимое добавлено
Использован {{BookCat}}; пробелы; →К переименованию: снят шаблон после переименования. |
DannyS712 (обсуждение | вклад) м <source> -> <syntaxhighlight> (phab:T237267) |
||
| Строка 1: | Строка 1: | ||
== Реализация тестирования простоты на С++ == |
== Реализация тестирования простоты на С++ == |
||
< |
<syntaxhighlight lang="cpp"> |
||
bool is_prime(int n) { |
bool is_prime(int n) { |
||
if (n <= 1) |
if (n <= 1) |
||
| Строка 13: | Строка 13: | ||
return true; |
return true; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== Нахождение всех простых до заданного ''N'' на С++ == |
== Нахождение всех простых до заданного ''N'' на С++ == |
||
Для этого воспользуемся тестированием на простоту, но не будем перебирать все делители до корня. Для упрощения будем проверять на делимость только простыми. Для этого заведем вектор целых чисел 'prime'. |
Для этого воспользуемся тестированием на простоту, но не будем перебирать все делители до корня. Для упрощения будем проверять на делимость только простыми. Для этого заведем вектор целых чисел 'prime'. |
||
< |
<syntaxhighlight lang="cpp"> |
||
const int N = 1000*1000; |
const int N = 1000*1000; |
||
std::vector<int> prime(1, 2); |
std::vector<int> prime(1, 2); |
||
| Строка 31: | Строка 31: | ||
if (!was) prime.push_back(i); |
if (!was) prime.push_back(i); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== Поиск на JavaScript == |
== Поиск на JavaScript == |
||
< |
<syntaxhighlight lang="javascript"> |
||
nextPrime: |
nextPrime: |
||
for(var i=2; i<1000; i++) { |
for(var i=2; i<1000; i++) { |
||
| Строка 44: | Строка 44: | ||
alert(i); // простое |
alert(i); // простое |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
{{BookCat}} |
{{BookCat}} |
||
Текущая версия от 15:58, 16 апреля 2020
Реализация тестирования простоты на С++[править]
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); // простое
}