Project Euler Hint

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(10 12 ) mod 10 9 . 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 n...

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(10 12 ) mod 10 9 . First thing comes into mind is Sieve of Eratosthenes.  However, 10^12 equals to 1000G which would cost too much time/space in a average laptop.  1, One thing comes into my mind is that obviously, Prime > 10^6 is only going to be count once. Therefore, take the S(100) as an example; S(100)= 2*50 + 3*17 + 5*7 + 7*4 + sum(prime < 100) - sum(prime < 10) (Note: sum(prime < N) is calculable in wolfram alpha, we don't have to worry about that part at least.) 2, Now let us take a look at the smallest primes. //Define sum_p(P) = count_p(P)*P; //Define count_p(P) = count of smpf(i)=P; We don't need to worry about prime(1) = 2. Because there will always be sum_p(...