Hii,i was trying to solve some problems in which i encountered one saying to find sum of digits of all prime numbers upto a number say n.I cannot solve it using normal method which is large.Can someone tell any logic to solve it.
-
-
you can use Sieve of Rrathosthenes.
First create an array of booleans size n where all of it is set to true
Then coss out all multiples of 2, that means, set array[4], array[6], array[8] etc to false, up to square root of n.
Then coss out all multiples of 3, that means, set array[6], array[9], array[12] etc to false, up to square root of n.
Skip 4, because array[4] is already crossed out.
Then coss out all multiples of 5, etc. etc. Do this for all multiples up to sqare root of n.
Now you only have prime numers remaining in your array.
The next task is easy: just loop through your remaining prime numbers and sum up their digits.
Done! -
Any other better algorithm by the way i think it was upto n not square root of n .Comment
-
The Sieve of Eratosthenes is one of the most effective algorithms. Just look it up in Wikipedia.
I bet you will not find one which is simpler and faster.
It definitely is square root of N.
(But crossing out is for the WHOLE array, not parts of it. I wrote that wrong in my previous forum entry)
Example: find all prime numbers up to 100. Square root of 100 is 10. So if you reach 10 after crossing out all 7's, it's done. Just think about it. The next prime would be 11. Have we crossed out all 11's already? Yes!- 2*11=22 (crossed out all 2's already),
- 3*11=33 (crossed out all 3's already),
- ...,
- 7*11=77 (crossed out all 7's already),
- 8*11=88 (crossed out all 8's already by crossing out all 2's),
- 9*11=99 (crossed out all 9's already by crossing out all 3's),
- 10*11=110 (already bigger than 100),
Comment
Comment