# Prime Numbers Between Two Numbers

Fastest code that print all `prime numbers` between two given numbers ?

Not necessary shortest.

Range may be any two numbers between `1` and `1e9` (one billion).

Time limit: 6s

Source limit: 50000B

-
fastest is not a easy to measure metric, also in what range should we consider this, up to 2^31 or arbitrarily large – ratchet freak Jan 10 '12 at 19:04
possible duplicate of Sum of primes between given range – mellamokb Jan 10 '12 at 20:08
I want the fastest one... – Arya Jan 10 '12 at 20:16
Since your winning criteria is fastest please remove the code-golf tag. What OS are you going to run the speed tests on? How much ram and what cpu? Are you able to accept any language when you run the tests or should we limit ourselves to certain ones? How will you generate the test cases? (I assume you will run multiple tests for multiple ranges, correct?) – Steven Rumbalski Jan 10 '12 at 20:22
@PaulR, the reason is easy to fathom: it's to stop someone hard-coding an array of all the primes and then using searches (binary chop with initial values determined using the known distribution of primes). – Peter Taylor Jan 10 '12 at 21:56

## J

``````n=.".1!:1]3
p:>:^:(_1 p:{.n)i.(_1 p:{:n)-(_1 p:{.n)
``````

I was surprised how quickly this worked when I gave it `10 1000000000` as an input. I guess it's heavily optimized for this kind of thing.

-
how long did it took for your code? – Ali.S Jan 11 '12 at 9:41
A few seconds. I don't have a J console installed on my work computer so I'll have to wait until later to give a more precise answer. – Gareth Jan 11 '12 at 10:13
I think I'll need to learn J (no easy task!) just to blow my co-workers minds. – Steven Rumbalski Jan 11 '12 at 16:09
@StevenRumbalski I'm only just learning myself - got fed up of losing at code golf with my Scala answers. :-) – Gareth Jan 11 '12 at 16:21
@Gadjet About 10 seconds (measured unscientifically - "1 mississippi, 2 mississippi ..."). – Gareth Jan 11 '12 at 19:51

## C++

This code comes in at under 14 seconds worst-case (min=0, max=1e9, with disabling the `printf`. Add an extra 10 seconds for `printf` piped to `/dev/null`). I'm not sure 6 seconds is achievable (except maybe with multiple threads).

``````#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define LOG_WORDBITS 6
#define WORDBITS 64
typedef uint64_t word;

int main(int argc, char *argv[]) {
int min = atoi(argv[1]);
int max = atoi(argv[2]);
if (min <= 2) { printf("2\n"); min = 3; }
if (!(min & 1)) min++;
if (!(max & 1)) max--;

// bit i in word array is set iff 2*i+3 is composite

int nbits = (max - 3) / 2 + 1;
int words = (nbits + WORDBITS - 1) / WORDBITS;
word *array = (word*)calloc(words, WORDBITS / 8);
for (int i = 0; i < nbits; i++) {
if (!((array[i >> LOG_WORDBITS] >> (i & WORDMASK)) & 1)) {
int p = 2 * i + 3;
if (p >= min) printf("%d\n", p);
if (p < 32768 && p * p <= max) {
if (p < 64) {
// dense sieving

// precompute pattern
word *x = (word*)calloc(p, WORDBITS / 8);
for (int j = 0; j < WORDBITS * p; j++) {
if ((2*j+3)%p == 0) x[j >> LOG_WORDBITS] |= 1LL << (j & WORDMASK);
}

// apply pattern
int z = 0;
for (int j = 0; j < words; j++) {
array[j] |= x[z];
z++;
if (z == p) z = 0;
}
free(x);
} else {
// sparse sieving
for (int j = 2 * i * i + 6 * i + 3; j < nbits; j += 2 * i + 3) {
array[j >> LOG_WORDBITS] |= 1LL << (j & WORDMASK);
}
}
}
}
}
}
``````
-
try optimizing your code using VC, gcc couldn't optimize my code, but using VC I achieved 6s without printing results. – Ali.S Jan 13 '12 at 15:27

## C++, 3.3 seconds

Ok, this version can make the 6 second limit by a good margin. By default it computes the sum of the indicated primes, just uncomment the `printf`s for the actual primes.

``````#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <vector>
using namespace std;

#define SIEVEBITS 17
#define SIEVESIZE (1<<SIEVEBITS)

uint8_t sieve[SIEVESIZE];

int main(int argc, char *argv[]) {
int low = atoi(argv[1]);
int high = atoi(argv[2]);
uint64_t sum = 0;

// handle 2 separately
if (low <= 2 && 2 <= high) {
//printf("2\n");
sum += 2;
}

// generate odd primes up to sqrt(1e9) = 31622
vector<int> oddprimes;
for (int p = 3; p < 31622; p += 2) {
bool prime = true;
for (int i = 3; i * i <= p; i += 2) {
if (p % i == 0) {
prime = false;
break;
}
}
if (prime) {
oddprimes.push_back(p);
if (low <= p && p <= high) {
//printf("%d\n", p);
sum += p;
}
}
}
if (low < 31622) low = 31622;

// sieve for remaining primes.  The entry at index i in the sieve
// represents the odd number 2 * (base + i) + 1.
for (int base = low / 2; base <= high / 2; base += SIEVESIZE) {
memset(sieve, 0, SIEVESIZE);
for (vector<int>::const_iterator i = oddprimes.begin(); i != oddprimes.end(); ++i) {
int p = *i;
int offset = (2 * base + 1) % p;
if (offset != 0) {
if (offset & 1) {
offset = (p - offset) >> 1;
} else {
offset = p - (offset >> 1);
}
}
for (int j = offset; j < SIEVESIZE; j += p) sieve[j] = 1;
}
for (int i = 0; i < SIEVESIZE; i++) {
int p = 2 * (base + i) + 1;
if (!sieve[i] && p <= high) {
//printf("%d\n", p);
sum += p;
}
}
}
printf("sum %llu\n", sum);
}
``````
-

## C

``````#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
int i,j;
int from=atoi(argv[1]);
int to=atoi(argv[2]);
int *sieve=(int *)calloc(to+1,sizeof(int));
for(i=2;i<=to;i++)
{
if(sieve[i]==0)
{
if(i>=from)
{
printf("%d ",i);
}
if(i*i<=to)
{
for(j=i;j<=to;j+=i)
{
sieve[j]=1;
}
}
}
}
printf("\n");
free(sieve);
return 0;
}
``````

Uses the Sieve of Eratosthenes to generate the primes and outputs them as it's doing so. Will fare worse against cleverer algorithms when the start number is very large.

Edit: I should note that I came up with this answer before the 6 second time limit appeared. My program meets that limit for max numbers up to around 100000000 but goes into a period of deep contemplation when you try 1000000000. :-S

-
I think it needs more than 1 day to give results for numbers as big as stated! – Ali.S Jan 10 '12 at 21:27
those conditions were added at "2012-01-10 20:26:25z" while you answered at "2012-01-10 20:33:47z", they were their while you posted your answer. but those are some impossible conditions, so don't worry about that! – Ali.S Jan 10 '12 at 21:37
You really need 64 bit ints for this if you're going to support the required range of up to 10000000000 (1e10). – Paul R Jan 10 '12 at 21:49
I think you also have some indexing problems - you need to correct for the `from` offset when accessing `sieve[]`. Also make sure that you're not attempting to access `sieve[]` outside its bounds. – Paul R Jan 10 '12 at 21:53
@Gajet I read the question, then came up with an answer, then posted it, then saw that the question had changed. But I'm relatively happy with my answer and won't be attempting to make it faster - like you say, the new conditions are a bit stringent. :-) – Gareth Jan 10 '12 at 21:54

tested my code on a windows machine powered by intel 720QM, I've only timed preprocessing, since writing (to console) it self takes large amount of time.

# c++ : 110s9-10s 6-7s & 611MB 61MB ram

``````    #include <stdio.h>
#include <time.h>
#include <math.h>
#include <memory.h>

#define isprime(X) ((X)&1?(!(bank[(X)>>6]&(1<<(((X)&63)>>1)))):(X)==2)
#define sqr(X) ((X)*(X))
#define maxpossible     (1000000000L)

unsigned int bank[maxpossible/64];

int main()
{
int beg = time(0);
unsigned long i,k,a,b;
unsigned long d,x,maxpossible_2 = maxpossible>>1;
unsigned long maxpossiblesqrt = sqrt((double)maxpossible)+1;
memset(bank,0,sizeof(bank));
bank[0] ^= 1;
for(i=0;i<maxpossiblesqrt/64;i++)
for(k=0;k<32;k++)
if(!(bank[i]&(1<<k)))
{
d = (((i<<5)|k)<<1)+1;
for(x=sqr(d)>>1;x<maxpossible_2;x+=d)
bank[x>>5]|=(1<<(x&31));
}
printf("preprocessing needed %d seconds\n" ,time(0) - beg);
printf("enter two positive number lower than %d\n" ,maxpossible );
scanf("%d %d" ,&a ,&b);
if (a<2)
a=2;
if (!(a&1))
printf(a++==2?"2\n":"");
int p=0;
for(i=a;i<=b;i+=2)
{
if(isprime(i))
{
printf(" %d",i);
p++;
if(p==8)
{
printf(" \n");
p=0;
}
}
}
}
``````

my code now compiles both in C++ and C (i've used c++ compiler myself), also fixed a small bug! some explaination:

to save if a number is prime or not you only need 1 bit, so you can easily reduce size of data needed to store if a number is prime by 8 if you use all 8 bits in each byte.

and besides the only even number which is prime is 2, so I can omit all the even numbers and only save if odd numbers are prime.

now how `isprime` works:

it first checks if a number is odd by computing `((X)&1)`, if a number is odd the result is 1 otherwise it's zero (note that odd numbers have 1 in their last bit).

• in case of even number I can easily check if `(X)==2` and it's the same as checking if an even number is prime

• in case of odd number I have to look into my table, first I need to find out which cell contains data for (X), and then which bit is telling if my number is prime. as I explained each cell contains 8 bits so 8 numbers and even numbers are completely off my list. so `(X)>>4` meaning `(X)` without it's 4 first bits generates cell number.
then to find out bit location I use (1<<(((X)&14)>>1)) which means : only keep bit 2,3 and 4 of my number, shift right 1 place and put data in bits 1,2 and 3 respectively. so far `(((X)&14)>>1)` it generates bit number the next step is to create a mask that checks only for that specific bit `(1<<(((X)&14)>>1))` it means shift a number with single first bit as true `(((X)&14)>>1)` places to left. in the end it's only checking if that specific mask applied to chosen data cell is true or false, which is done by only applying the mask by bitwise & operator (c++ itself checks if result is none-zero)

if you got how isprime works the rest is easy, it's using Sieve of Eratosthenes method to eliminate all none-prime numbers. the only thing I can mention is if p is a prime number, it starts from p^2 with step of size 2*p and eliminates all none-prime numbers to increase performance.

-
Could I get an explanation on how `isprime(X) ((X)&1?(bank[(X)>>4]&(1<<(((X)&14)>>1))):(X)==2)` works? – Mr. Llama Jan 10 '12 at 21:01

## Q (91)

``````d:{s where 0<>s:{if[2=x;:x];\$[0=x mod 2;0;0=min x mod 2+til floor sqrt x;0;x]}each x+til y}
``````

Sample Usage:

``````q)d[1;100]
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
``````
-
``````!@:"^&<=upper:than->lower**&%\$\$%??{}{[]}::1&;
``````
-
I've formatted your code (just put four spaces before each line of code to create a code block), but I couldn't label it with the correct language name as I can't figure out what it is... – Gareth Jan 5 '13 at 17:33
Which language is that? – Knerd Nov 23 '14 at 20:14

## C - 310 bytes

``````#include<stdio.h>
#include<conio.h>

void main()
{

int start,end,i=0;
clrscr();

printf("Enter the range");
scanf("%d%d",&start,&end);

while(start<=end)
{
i=3;
if(start==2)
printf("%d",start);

while(i<=start)
{
if(start%i==0)
break;
i++;
}
if(i==start)
printf("%d",start);
start++;
}
getch();
}
``````
-
Hi and welcome! Could you please add the language and in this case the average time your code needs to solve the problem? – air_blob Feb 19 '13 at 10:58

## Clojure - prime test based on Wilson's theorem

Wilson's theorem states that a number `n` is prime if `((n-1)! + 1) mod n = 0`. This version makes use of Clojure's handy support for Java BigNum values and operations (the `*'` and `+'` operators) and its speed is thus heavily dependent on the Java BigNum class. This implementation takes advantage of the fact that the numbers to be checked will always increase and will always be odd (except for 2, which is special-cased), and thus keeps the value of `(n-1)!` as a running total instead of recomputing it for each new value.

``````(defn find-primes-between [t1 t2]
(loop [c (if (>= 2 t1) [2] [])    ; collection of primes found thus far
n (cond
(<= t1 2) 3
(odd? t1) t1
:else (inc t1))
f (apply *' (range 2 n))   ; (n-1)!
l (mod n 10)]              ; last digit of n
(if (> n t2)
(if (or (not= l 5) (< n 7))   ; else if last digit of n is not 5
(if (= (mod (+' f 1) n) 0)  ; then - Wilson's theorem - a number is prime if (n-1)! + 1 mod n = 0
(recur (conj c n) (+' n 2) (*' f n (+' n 1)) (mod (+ l 2) 10))      ; n is prime - recur with updated collection, next number, and updated running (n-1)!
(recur c          (+' n 2) (*' f n (+' n 1)) (mod (+ l 2) 10)))     ; n is not prime - recur with current collection, next number, and updated running (n-1)!
(recur   c          (+' n 2) (*' f n (+' n 1)) (mod (+ l 2) 10))) ))) ; else skip mod of large number when last-digit = 5 case
``````

While not particularly fast I think it's an interesting recursive implementation. Caveat: as with any Lisp-style implementation there's a substantial risk of critical depletion of the Strategic Parenthesis Reserve, but I think the ends justify the means. :-)

## Edit

The above doesn't take advantage of multiple cores so here's a wrapper which will divide the work among four threads and then merge the results:

``````(defn find-primes-between-threaded [t1 t2]
(let [ range-end (map #(int (* (- (inc t2) t1) %)) [ 0.40 0.70 0.90 ]) ]
(sort (apply concat (pvalues (find-primes-between t1                        (first range-end))
(find-primes-between (inc (first range-end))   (second range-end))
(find-primes-between (inc (second range-end))  (last range-end))
(find-primes-between (inc (last range-end))    t2))))))
``````

The improvement from using multiple threads (which appear to terminate at approximately the same time, based on watching them run in the Windows Task Manager) isn't as large as I'd hoped: the time to run a scan for all primes from 1 to 125,000 is about 83 seconds when run in a single thread, and is reduced to about 67 seconds when running in four threads. Still, any improvement is better than no improvement. :-)

Share and enjoy.

-

## C++ code || prime test !!! || based on miller non deterministic algorithm

``````#include <iostream>
#include <cstring>
#include <cstdlib>
#define ll long long
using namespace std;

/*
* calculates (a * b) % c taking into account that a * b might overflow
*/
ll mulmod(ll a, ll b, ll mod)
{
ll x = 0,y = a % mod;
while (b > 0)
{
if (b % 2 == 1)
{
x = (x + y) % mod;
}
y = (y * 2) % mod;
b /= 2;
}
return x % mod;
}
/*
* modular exponentiation
*/
ll modulo(ll base, ll exponent, ll mod)
{
ll x = 1;
ll y = base;
while (exponent > 0)
{
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}

/*
* Miller-Rabin primality test, iteration signifies the accuracy
*/
bool Miller(ll p,int iteration)
{
if (p < 2)
{
return false;
}
if (p != 2 && p % 2==0)
{
return false;
}
ll s = p - 1;
while (s % 2 == 0)
{
s /= 2;
}
for (int i = 0; i < iteration; i++)
{
ll a = rand() % (p - 1) + 1, temp = s;
ll mod = modulo(a, temp, p);
while (temp != p - 1 && mod != 1 && mod != p - 1)
{
mod = mulmod(mod, mod, p);
temp *= 2;
}
if (mod != p - 1 && temp % 2 == 0)
{
return false;
}
}
return true;
}
//Main
int main()
{
int iteration = 10; // increase it for accuracy
ll n,a,b;
cin>>n;
for(ll j = 0;j<n;j++)
{
cin >>a>>b;
for(ll num = a;num <=b;num++)
{
if (Miller(num, iteration))
cout<<num<<endl;
}
cout << endl;
}

return 0;
}
``````
-
it is in c++ ........based on miller non deterministic algorithm – Debashish Nov 23 '14 at 19:42