Ranajoy Saha

Ranch Hand

Posts: 105

2

posted 3 years ago

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

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

posted 3 years ago

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.

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Campbell Ritchie

Marshal

Posts: 56595

172

posted 3 years ago

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.

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

posted 3 years ago

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 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

posted 3 years ago

I'm sorry.

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%.

And I missed it.Piet Souris wrote: . . . He did, see under his code.

I'm sorry.

You will also see some poor solutions. I am pretty sure you could write a better Sieve yourself.

. . . If you look at solutions to the problems of the Project Euler, you will see incredible smart methods and algorithms. . . .

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

posted 3 years ago

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