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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
перенесено из w:Перебор делителей
 
Строка 29: Строка 29:
}
}
</source>
</source>

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

Версия от 10:24, 31 марта 2011

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

bool is_prime(int n) {
    if (n <= 1)
        return false;
 
    for (int j = 2; j * j <= n; j++)
         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 % v[j] == 0){
			was = true; 
			break;
		}
	if (!was) prime.push_back(i);
}