Реализации алгоритмов/Перебор делителей: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Использован {{BookCat}}; пробелы; →‎К переименованию: снят шаблон после переименования.
Строка 1: Строка 1:
{{К переименованию |2014-11-21|Реализации алгоритмов/Перебор делителей}}

== Реализация тестирования простоты на С++ ==
== Реализация тестирования простоты на С++ ==
<source lang="cpp">
<source lang="cpp">
Строка 12: Строка 10:
for (int j = 3; j * j <= n; j+=2)
for (int j = 3; j * j <= n; j+=2)
if (n % j == 0) return false;
if (n % j == 0) return false;

return true;
return true;
}
}
Строка 25: Строка 23:
int was = false;
int was = false;
for (int j = 0; j < prime.size(); ++j)
for (int j = 0; j < prime.size(); ++j)
if (prime[j]*prime[j] > i)
if (prime[j]*prime[j] > i)
break;
break;
else if (i % prime[j] == 0){
else if (i % prime[j] == 0){
was = true;
was = true;
break;
break;
}
}
Строка 34: Строка 32:
}
}
</source>
</source>

== Поиск на javascript ==
== Поиск на JavaScript ==
<source lang="javascript">
<source lang="javascript">
nextPrime:
nextPrime:
for(var i=2; i<1000; i++) {
for(var i=2; i<1000; i++) {

for(var j=2; j<i; j++) {
for(var j=2; j<i; j++) {
if ( i % j == 0) continue nextPrime;
if ( i % j == 0) continue nextPrime;
}
}

alert(i); // простое
alert(i); // простое
}
}
</source>
</source>

[[Категория:Программирование]]
{{BookCat}}

Версия от 12:51, 7 декабря 2014

Реализация тестирования простоты на С++

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);  // простое
}