The problem statement
We need to find the number of divisors of numbers from 1 to 10^6 and then check if that number is a multiplication of 2 distinct primes or not. Fir of all we need to get all the prime numbers, we will use the sieve or Eratosphen. We need to do one more thing in our process of finding the prime numbers. Let us have an array named A[] where A[i] shows the number of divisors of i. Now Initially all the elements of A have a value of 1.(we consider that we had already taken the number 1 as a divisor of every number). Now when we are doing our prime search we need to do the divisor count as well. Here is how prime search worked, when we had a number which was not marked we considered it as prime and then we looped over all the numbers which are divisible to that number and marked them as primes. While doing that we also need to increase the current number of divisors with 1. Here is an example
we are now on number 2 which sis a prime that means that we must loop over the number 4,6,8,10...1000000 and mark them as not primes, also we will increase A[4],A[6],A[8].....,A[1000000] with 1 by saying that all these numbers are divisible on 2.
After calculating the primes and the number of divisors of 1 million numbers we can move on to the second step by checking if the elements in the array A have the form of A[i]=p*q (p and q are distinct primes). First of all we need to keep the prime numbers in some array. Then for every number in the array A[i] we need to do a brute force loop. We need to loop over all the primes numbers starting from the lowest and check for the condition.
Check out the source code for a better understanding.
We need to find the number of divisors of numbers from 1 to 10^6 and then check if that number is a multiplication of 2 distinct primes or not. Fir of all we need to get all the prime numbers, we will use the sieve or Eratosphen. We need to do one more thing in our process of finding the prime numbers. Let us have an array named A[] where A[i] shows the number of divisors of i. Now Initially all the elements of A have a value of 1.(we consider that we had already taken the number 1 as a divisor of every number). Now when we are doing our prime search we need to do the divisor count as well. Here is how prime search worked, when we had a number which was not marked we considered it as prime and then we looped over all the numbers which are divisible to that number and marked them as primes. While doing that we also need to increase the current number of divisors with 1. Here is an example
we are now on number 2 which sis a prime that means that we must loop over the number 4,6,8,10...1000000 and mark them as not primes, also we will increase A[4],A[6],A[8].....,A[1000000] with 1 by saying that all these numbers are divisible on 2.
After calculating the primes and the number of divisors of 1 million numbers we can move on to the second step by checking if the elements in the array A have the form of A[i]=p*q (p and q are distinct primes). First of all we need to keep the prime numbers in some array. Then for every number in the array A[i] we need to do a brute force loop. We need to loop over all the primes numbers starting from the lowest and check for the condition.
Check out the source code for a better understanding.
No comments:
Post a Comment