Prime Factor Coding Challenge

[altenbach]

---

@Bruce Ammons wrote:

FYI, I checked with my program.  The factors of your number are 5 and 1775249506851503.

---

Hey, I just figured that myself! My program actually gets the higher factor but it exceed the I32 range for the output. 😞

So the correct challenge description:

• The input is a 16 decimal digit DBL numbers, but in case of >2^53 it would be possibly coerced to even.
• The highest possible prime factor ithat is allowed to occur in the above number is 99999989.

My version fulfills these requirements already, so I'm fine. 🙂

How should we do error handling? Currently I return an empty array if the input is more than 16 digits.

It would have been nicer to represent the prime factors also as DBL so all inputs are legal, even 16 digit primes (only ONE prime factor) or numbers containing prime factors up to 16 digits 😉 Except for the I32 coercion, my code would handle all these without any speed penalty.

Is it too late to loosen this unecessary restriction and allow all possible prime factors?

See for example the my correct result for 8876247534257517 IF I set the output to DBL, one of the factors is 14 digits!:

Soo...., why make artificial restrictions to 8 digit factors??? It does not simplify the problem.

I'll clean it up a bit and submit it. It's pretty primitive so I'm sure there are much faster algorithms. 🙂

Message Edited by altenbach on 09-20-2005 11:18 PM

[BruceAmmons]

The main reason for the 8 digit limit on the prime factors is so that I (and you) can easily and quickly generate numbers and solutions.  It is very fast to check the prime factors of an 8 digit number.

I don't mind if your program outputs DBL values for the prime factors.  This will make your program more versatile, and will let you factor ANY integer that can be represented by a DBL.  However, I will stick to my limit of 8 digit primes since that is how I stated the original challenge.  I don't want to change any rules unless it is necessary.  I will just convert your output to I32 when I test it.

I'm not too concerned about error checking.  I won't be testing for invalid inputs, so there should be no errors.  Perhaps round the input to the nearest integer and check if it is greater than zero.  If it is factor it, otherwise return an empty array.  You can actually factor a DBL integer with more than 16 digits, and the largest prime will still be 16 digits or less.

Bruce

[BruceAmmons]

Regarding submitting a solution:

Please test your solution with the program I posted earlier before submitting it!!!  It would be helpful if you use the same vi name I used for my template.

Zip your files up, and make sure your identifying information is in the zip file name (your name is simplest).  This will make it easy to keep track of submissions.

If you email me your solution, I will test it using the same program that I posted, and let you know what your time was.  I will not comment on programming content/style for any entries, and I won't provide any suggestions for improvement.  The only thing I will give you is your time.

I will accept any entries either emailed to me or submitted via NI.  I don't know if I will see the ones submitted through NI before the competition is over, though.

At some point after we have enough entries, I will probably start posting the top results.

I will be using a different list of numbers for the official final results, but I wouldn't expect the results to vary much.

Bruce

[BruceAmmons]

Please email your submission to: challenge@ammonsengineering.com

Bruce

[shoneill]

Am I the only one who thinks that as soon as there are slightly better results posted, Altenbach's just going to trump them again?

I have to admit, after skipping the last couple of challenges, this one has me interested again.

Let's see what we can do.

Shane.

[ohw313]

HI Bruce,

NIce Challenge.

Ah, Prime Crunching, who says it is not a healthy hobbie(Okay, that was sad)

My time is now 53 sec(P4, 3GHZ, 3GB)

I have a few more ideas and will continue the attack.

Am I in the ballpark or am I the snail of the group again.

Jurgen 313

[altenbach]

Jurgen,

Have you submitted it? I just submitted mine. Bruce can thest them on a neutral machine.

Shane instructed me above  to tell you that my submission might be a bit faster on a slower computer (1GHz PIII, 512MB RAM, XP, LabVIEW 7.1). 😉 ... so yes, you should be able to go a "little" bit faster. 🙂 Why can't you just get rid of that jump at N=88? 😮

I think I hit the ceiling with my current very simple algoritm so I would have to get a bit more creative. I'm not sure if I have time, though.

My solution has a file size of ~85kB and the only prime number I don't calculate from scratch is "2".

How big is your file? Happy prime huntung. 😄

[ohw313]

Ooeps. Found a silly mistake(It was of course a really speedily done draft)

Time is now down to:  37 seconds.

Will submit to Bruce and soon as try a few more little tricks(Will save getting desperate and writing a new prime generation algorithm for later)

 Enjoy the hunt.

[shoneill]

BTW,

Any idea of a closing date for entries?  An estimate would be nice so that I can plan if I am going to be locked away this weekend or not ;).

I've made some progress, but I'm not up there yet.  Will try something different.

At the moment, the first run takes way too long (just over 30 seconds - Pentium IV 2.8GHz, 1GB RAM).  Each subsequent takes around 8 seconds.

I reckon there's still plenty of room for improvement.

Shane.

[BruceAmmons]

As stated in the coding challenge, the deadline is Friday, Dec. 2.

Bruce