Hint 2 Project Euler Problem 521 Smallest prime factor
Smallest prime factor
Problem 521
Let smpf(n) be the smallest prime factor of n.
smpf(91)=7 because 91=7×13 and smpf(45)=3 because 45=3×3×5.
Let S(n) be the sum of smpf(i) for 2 ≤ i ≤ n.
E.g. S(100)=1257.
Find S(1012) mod 109.
Last time I mentioned "Sieve of Eratosthenes". However, the memory of a personal laptop I can afford only goes around 10^9 considering the sieve takes at least 1 bit for each number for labeling purpose. And 10^9 = 1/8 Gigabyte of memory at least. Since it won't go up to 10^12 anyway, I can play it safe and stick with 10^6 instead of trying to push it for the moment.
First, it is obvious that min prime < 10^6 unless the number itself is a prime.
Second, assume we set a flag for IsPrime[1] ~ IsPrime[10^6] which takes around 1M of memory. flag = 1 indicate that it is a prime, flag = 0 indicate it is not a prime.
Below is just an illustration.
//Init
IsPrime{}=1;
IsPrime[1]=0;
//Everytime we encounter a prime(the next number with IsPrime still equals 1)
IsPrime[P]=1;
Sum+=P;
Eliminate all numbers that can be divided by P by
{set their flag to 0; sum+=P;}
//Find the next prime and repeat
What happened after we reached 10^6?
Now that we have all the primes under 10^6, we can take advantage of that info. A slight alteration to the algorithm illustrated above would do the trick.
//Init
Save the primes we found into new const array PrimeunderMillion[];
Million+=1;
IsPrime{}=1;
For each PrimeunderMillion[i]
Rem=10^6 mod PrimeunderMillion[i];
Set flags to 0 starting from IsPrime[PrimeunderMillion[i]-Rem], every PrimeunderMillion[i].
sum+=PrimeunderMillion[i];
//After all is done
sum+=n if IsPrime[n]==1;
Repeat this until Million==10^6 and I believe that we have our sum ready.
---------------------
The opinion above is original and unproven work. Please correct me if I made a mistake.
smpf(91)=7 because 91=7×13 and smpf(45)=3 because 45=3×3×5.
Let S(n) be the sum of smpf(i) for 2 ≤ i ≤ n.
E.g. S(100)=1257.
Find S(1012) mod 109.
Last time I mentioned "Sieve of Eratosthenes". However, the memory of a personal laptop I can afford only goes around 10^9 considering the sieve takes at least 1 bit for each number for labeling purpose. And 10^9 = 1/8 Gigabyte of memory at least. Since it won't go up to 10^12 anyway, I can play it safe and stick with 10^6 instead of trying to push it for the moment.
First, it is obvious that min prime < 10^6 unless the number itself is a prime.
Second, assume we set a flag for IsPrime[1] ~ IsPrime[10^6] which takes around 1M of memory. flag = 1 indicate that it is a prime, flag = 0 indicate it is not a prime.
Below is just an illustration.
//Init
IsPrime{}=1;
IsPrime[1]=0;
//Everytime we encounter a prime(the next number with IsPrime still equals 1)
IsPrime[P]=1;
Sum+=P;
Eliminate all numbers that can be divided by P by
{set their flag to 0; sum+=P;}
//Find the next prime and repeat
What happened after we reached 10^6?
Now that we have all the primes under 10^6, we can take advantage of that info. A slight alteration to the algorithm illustrated above would do the trick.
//Init
Save the primes we found into new const array PrimeunderMillion[];
Million+=1;
IsPrime{}=1;
For each PrimeunderMillion[i]
Rem=10^6 mod PrimeunderMillion[i];
Set flags to 0 starting from IsPrime[PrimeunderMillion[i]-Rem], every PrimeunderMillion[i].
sum+=PrimeunderMillion[i];
//After all is done
sum+=n if IsPrime[n]==1;
Repeat this until Million==10^6 and I believe that we have our sum ready.
---------------------
The opinion above is original and unproven work. Please correct me if I made a mistake.
Comments
Post a Comment