• Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help understanding the usage of Sieve of Eratosthenes for finding primes faster  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Everyone

I found this method from the same link from which I found the Pandigital method. This method uses the algorithm of sieve of eratosthenes who was a greek mathematician and showed how to find prime numbers by taking an individual number and finding the multiples of it and cut them out for they will not be a prime number. From what I've seen this program gives the results much faster than the traditional way of searching for prime numbers by diving that number by the digits upto half of that number and check for divisiblity.

Well, here's the code



As seen from the full program on the site http://www.mathblog.dk/files/euler/Problem41.cs this program was formely writen in C++ and from there I've scrapped out this method as the syntax are corresponding to that of Java, but one problem I faced was in finding the BitArray class in Java. It would be of great help if someone throws light if any such method exists in Java. I was unable to dry run this piece of code because I was unable to understand the approach of this program to find the prime numbers. It would be of great help if someone points out how it functions.

Regards,
Ranajoy Saha
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So a quick look at the java API finds a class called BitSet. A VERY quick look at the code you posted and the documentation seems to indicate it would work.

You really should bookmark the API for the version of Java you are using (above is java 7). Familiarize yourself with it, how to read it, what is in there...you can save yourself a LOT of time if you check there.
 
Campbell Ritchie
Marshal
Posts: 56595
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did it really say up to half that number? Please always tell us where you found such code.

The Sieve does not find whether a particular number is prime any faster than any other way. What it does is find all the prime numbers up to a certain maximum. It is probably not faster for one number, but it will find all primes up to 1000000 for example in under a second.
Where does 1.03866 come from? Numbers which appear mysteriously like that are called magic numbers and they can make the code very confusing to read. Also difficult to maintain.
Is that Java® code or C#? The capital letters look like C#. I suspect BitArray is the C# counterpart of BitSet.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Did it really say up to half that number? Please always tell us where you found such code.
(...)

He did, see under his code.

@Ranajoy,

as you say, you also had this question about a routine you found for pandigital numbers. If you look at solutions to the problems of the Project Euler, you will see
incredible smart methods and algorithms. Problem is that you will not be learning much of this. My advise is: come up with your own solutions. Why not write your own
Sieve, even if your method may end up (much) slower than other solutions. I know from experience: writing your own library full of handy methods, and improving them
as you gain experience, wil be time much better spent.
 
Campbell Ritchie
Marshal
Posts: 56595
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote: . . . He did, see under his code.
And I missed it.
I'm sorry.

. . . If you look at solutions to the problems of the Project Euler, you will see incredible smart methods and algorithms. . . .
You will also see some poor solutions. I am pretty sure you could write a better Sieve yourself.

Project Euler (PE) exercises are not about lots of programming, but about thinking. That is why you are supposed to be able to solve them with very short programs. For example, there is a simple way of reducing the search space in the link you quoted by over 98%.
 
Campbell Ritchie
Marshal
Posts: 56595
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you looked up how a Sieve works? You start with the smallest prime number and step along your row of numbers removing every multiple of it. Then you go back to the beginning and the smallest number remaining above the last prime is prime. Then you repeat the procedure until you are sure no composite numbers remain. There is an example on Wikipedia. I also found one on YouTube but you may need an aspirin after watching it
 
Campbell Ritchie
Marshal
Posts: 56595
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My solution runs in approx 1.2seconds and occupies 74 lines including whitespace and single { }. It gave the answer 76527476523. I might have copied that wrongly.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!