Реализации алгоритмов/Перебор делителей

Материал из Викиучебника — открытых книг для открытого мира

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

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