Простые числа. Решето Эратосфена
Перейти к навигации
Перейти к поиску
Проверка числа на простоту, O(sqrt(N))
bool isPrime(int n) {
if (n < 2)
return 0;
for (long long d = 2; d * d <= n; d++)
if (n % d == 0)
return 0;
return 1;
}
|
bool isPrime(int n) {
if (n < 2)
return 0;
static vector<int> primes = getPrimes(1e5);
for (int i = 0; 1LL * primes[i] * primes[i] <= n; i++)
if (n % primes[i] == 0)
return 0;
return 1;
}
|
Получение списка делителей числа, O(sqrt(N))
vector<int> getDivisors(int n) {
vector<int> divisors;
for (long long d = 1; d * d <= n; d++) {
if (n % d == 0) {
divisors.push_back(d);
if (d * d != n)
divisors.push_back(n / d);
}
}
sort(divisors.begin(), divisors.end());
return divisors;
}
|
vector<int> getPrimeDivisors(int n) {
vector<int> primeDivisors;
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) {
primeDivisors.push_back(d);
while (n % d == 0)
n /= d;
}
}
if (n != 1)
primeDivisors.push_back(n);
return primeDivisors;
}
|
Факторизация числа (получение списка простых делителей), O(sqrt(N))
vector<int> factorize(int n) {
vector<int> factorization;
for (long long d = 2; d * d <= n; d++) {
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
}
if (n != 1)
factorization.push_back(n);
return factorization;
}
|
map<int, int> factorize(int n) {
map<int, int> factorization;
for (long long d = 2; d * d <= n; d++) {
while (n % d == 0) {
factorization[d]++;
n /= d;
}
}
if (n != 1)
factorization[n]++;
return factorization;
}
|
Решето Эратосфена, O(NloglogN)
vector<int> getPrimes(int n) {
vector<int> isPrime(n + 1, 1), primes;
for (int i = 2; i < isPrime.size(); i++) {
if (isPrime[i]) {
primes.push_back(i);
for (long long j = 1LL * i * i; j < isPrime.size(); j += i)
isPrime[j] = 0;
}
}
return primes;
}
Решето Эратосфена, O(N)
vector<int> getPrimes(int n) {
vector<int> minDivisor(n + 1), primes;
for (int i = 2; i < minDivisor.size(); i++) {
if (!minDivisor[i]) {
minDivisor[i] = i;
primes.push_back(i);
}
for (int j = 0; j < primes.size() && primes[j] <= minDivisor[i] && 1LL * i * primes[j] < minDivisor.size(); j++)
minDivisor[i * primes[j]] = primes[j];
}
return primes;
}
Ссылки
Теория:
Код:
Задачи: