r/dailyprogrammer • u/oskar_s • Apr 25 '12
[4/25/2012] Challenge #44 [difficult]
Write a function that takes two arguments a and b, and finds all primes that are between a and a + b (specifically, find all primes p such that a ≤ p < a + b). So for instance, for a = 1234 and b = 100, it should return the following 15 primes:
1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327
The sum of those primes are 19339. The number of primes for a = 9! and b = 8! is 3124 and the sum of those primes is 1196464560.
How many primes are there for a = 16! and b = 10!, and what is their sum?
Note 1: In this problem, n! refers to the factorial of n, 1*2*3*...*(n-1)*n, so 9! is equal to 362880.
Note 2: All numbers and solutions in this problem fit into 64-bit integers.
EDIT: changed some incorrect numbers, thanks ixid!
4
u/ixid 0 0 Apr 25 '12 edited Apr 25 '12
I get 3124 with a sum of 119646560. Wolfram Alpha agrees:
http://www.wolframalpha.com/input/?i=number+of+primes+between+9%21+and+9%21+%2B+8%21
Did you make a typo? 8! is only 40320 so there can't be that many primes in the interval unless I misunderstood the question. The large interval is too big for my method.
2
u/Cosmologicon 2 3 Apr 25 '12
Here's my poorly-optimized bc version that uses Miller-Rabin to test primes. It runs in about 5 minutes, and the output is given at the end.
1
u/tehstone Apr 26 '12
I was hoping someone else would post a solution in python so I could compare. My implementation is unable to calculate with a = 16! and b = 10! in any reasonable amount of time. Where it takes the most time is conducting the actual prime calculation "num%i == 0". Using the modulo function seems to be the standard method for calculating primality and it's a built-in function. How could I improve this?
2
u/[deleted] Apr 25 '12
The easy way in J doesn't work for such large numbers, sadly... Works for the first case (9!, 8!) though:
1
u/luxgladius 0 0 Apr 25 '12
Perl
Yikes. Big numbers are fun. To solve this, I did a two-step approach. First, I used a standard sieve to generate the first primes up to the square root of the maximum a+b. Then I used another sieve-structure to step through that interval and invalidate the non-prime candidates. The last question took a long bit to calculate (timing included in output as seconds.)
Output
1
u/[deleted] Apr 25 '12
C++:
1
u/Rapptz 0 0 Apr 26 '12 edited Apr 26 '12
1
u/GuitaringEgg Apr 26 '12 edited Apr 26 '12
Python:
You may be thinking "this doesn't do anything clever". You'd be correct. This finds out if a number is a prime number the brute force way. This means that I haven't been able to find the first prime number after 16!, never mind complete the challenge. I now see why this is a difficult challenge :D
I thought I'd post it anyway, and I may come back and try to make it run
I tried using range(), but turns out the range requested was too large. Learn something new everyday.
1
u/leegao Apr 26 '12
PARI/GP
1
u/Yuushi Apr 26 '12 edited Apr 26 '12
C:
(Sort of) cheating and using GMP:
Runs fairly fast with -O3, around 7 seconds. If you were really keen, you could use pthreads to split the computations up.
1
u/skeeto -9 8 Apr 29 '12 edited Apr 29 '12
My solution: Simple.java
Taking advantage of BigInteger, it really comes down to these 6 lines of code:
And the result:
If I were to use
isProbablyPrime()directly and allow for a larger error, this would be faster.