Number Theory – III

Euler’s totient functionDescription:phi(N)counts the number of integers from1toNinclusive that are relatively prime toN.Implemention:let me remind you thatfactorizationis the way to represent given number as a product of primes. And it’s easy to see that for every number such representation is unique. For example:8 = 2311 = 1136 = 22* 32935 = 5 * 11 * 175136 = 24* 3 * 107So, implemention is based on factorization:int phi(int n) {
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
while (n % i == 0) {
n /= i;
}
res -= res / i;
}
}
if (n != 1) {
res -= res / n;
}
return res;
}It works inO(sqrt(N))time. How to make it faster read further.Modification of Sieve of Eratosthenes for fast factorizationImplemention:let’s see how we can factorizeNinO(sqrt(N))timevector<int> factorize(int n) {
vector<int> res;
for (int i = 2; i * i <= n; ++i) {
while (n % i == 0) {
res.push_back(i);
n /= i;
}
}
if (n != 1) {
res.push_back(n);
}
return res;
}At every step we are looking for a minimal prime number that divides our currentN. This is the main idea of Sieve’s modification. Let’s construct such array which inO(1)time will give us this number:int minPrime[n + 1];
for (int i = 2; i * i <= n; ++i) {
if (minPrime[i] == 0) { //if i is prime
for (int j = i * i; j <= n; j += i) {
if (minPrime[j] == 0) {
minPrime[j] = i;
}
}
}
}
for (int i = 2; i <= n; ++i) {
if (minPrime[i] == 0) {
minPrime[i] = i;
}
}Now we can factorizeNinO(log(N))time using this modification:vector<int> factorize(int n) {
vector<int> res;
while (n != 1) {
res.push_back(minPrime[n]);
n /= minPrime[n];
}
return res;
}Conditions:you can implement this modification only if you’re allowed to create an array of integers with sizeN.Advices:this approach is useful when you need to factorize a lot of times some not very large numbers. It’s not necessary to build such modified Sieve in every problem where you need to factorize something. Moreover you can’t build it for such largeNlike109or1012. So, use factorization inO(sqrt(N))instead.Cool fact:if factorization ofNisp1q1* p2q2* … * pkqkthenNhas(q1+ 1) * (q2+ 1) * … * (qk+ 1)distinct divisors.Sieve of Eratosthenes on the segmentSometimes you need to find all primes not in range[1…N]but in range[L…R], whereRis large enough.Conditions:you’re allowed to create an array of integers with size(R – L + 1).Implemention:bool isPrime[r – l + 1]; //filled by true
for (long long i = 2; i * i <= r; ++i) {
for (long long j = max(i * i, (l + (i – 1)) / i * i); j <= r; j += i) {
isPrime[j – l] = false;
}
}
for (long long i = max(l, 2); i <= r; ++i) {
if (isPrime[i – l]) {
//then i is prime
}
}The approximate comlexity isO(sqrt(R) * const)Advices:again it’s not necessary to build such Sieve if you need to check just several numbers for primality. Use the following function instead which works inO(sqrt(N))for every number:bool isPrime(int n) {
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *