PDA

View Full Version : Prime number finder



Recursive
12-11-2012, 05:16 AM
Made program that finds the ith prime number. I made it for projecteuler (http://projecteuler.net/problems). What it does is that it finds the ith prime. So if you want to know say what the 70th prime is, you just change a variable in the code and and when you run it, it will spit out that prime number. I have tweaked it as much as I can to make it run faster but I know many of you can do a better job than I. Here is the source code:

/*Owner: Re_cursive
*Date: 10/12/12*/

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

//function headers
uint mod_sqrt(uint );
bool isPrime(uint[], uint);
uint* extend_arr(uint [], int, uint);
FILE* infile = fopen("Divprime.txt", "w+");

int main()
{
int count = 1;//count starts at 1 because the array of primes already contains a prime (2)
int y;
int track;
int length = 1;
uint* array = new uint[length];//dynamically allocated array
array[0] = 2;

for (y = 3; count < 10001 ; y+=2)//<== change this count value to the ith prime you want
{
if (isPrime(array, y))
{
count++;//if it is prime, increase the counter by 1
track = y;
array = extend_arr(array, length, y);//Add the prime to our array by increasing the size and appending the value to the end of the array
length++;
}

}
fclose(infile);//When finished, close the file we were writing into
printf("\n%d %d\n", track, count);//print the final prime and it's position
return EXIT_SUCCESS;
}

//A sqrt function modified from the pow function in c++
uint mod_sqrt(uint num)
{
float num2 = num * 1.0;
num = pow(num2, 0.5) * 1;
return num;
}

//checks for primeness
bool isPrime(uint arr[], uint val)
{
uint B = mod_sqrt(val);
while( *arr <= B)//it will not check all primes in the array
{
if (val % *arr == 0)
{
fprintf(infile, "%d is divisible by %d \n", val, *arr);//print the faulty prime to a file with the value that divided it evenly
return false;
break;
}
arr++;
}
return true;
}

//take in an array of values, and return a new array with a new value
uint* extend_arr(uint arr[], int length, uint val)
{
uint* array2 = new uint[length + 1];//create the new array
for (int J = 0; J < length; J++)
array2[J] = arr[J];//fill it with the values from the previous array

array2[length] = val;//attach the new value to the end of it

delete[] arr;
arr = NULL;

return array2;//return the array
}

If you have eclipse or any software capable of compiling c/c++, you can just copy and paste everything into it and compile and run. Or you can save it as 'primes.cc' in notepad and compile and run it via terminal with (make sure you are in the dir where you saved the file):
g++ -g -o primes primes.cc
Then run it with either ./primes or time ./primes

Results from running it:


10001st prime:

104743 10001

real 0m0.291s
user 0m0.264s
sys 0m0.016s

100001st prime:

1299721 100001

real 0m27.629s
user 0m24.642s
sys 0m2.944s

I also ran it for 1000001st prime and that took like 50 mins (hence why I said, make it run faster) but it still produced the right number in the end ~15million.

Before I forget, it also creates a file in your directory (Divprime.txt) where it will store each non-prime that it checks and what number multiple of that number made it non prime. This can sort of give you a nice visual of where some primes and maybe you can make a better one.

One can also easily change this code to just check if a number is prime or if you don't know how to do that, this could also be a learning curve.


EDIT:

Made it faster by using vectors instead of arrays and here is new one:

#include <cstdio>
#include <vector>
#include <cmath>
#define MAX 1000001

int mod_sqrt(int );
void isPrime(std::vector<int> *, int );
int count = 1;

int main()
{
std::vector<int> array(1,2);

for (int y = 3; count < MAX ; y+=2)
isPrime(&array, y);

printf("\n%d %d\n", array.back(), count);
return 0;
}

int mod_sqrt(int num)
{
return (int) (pow(num, 0.5));
}


void isPrime(std::vector<int> *arr, int val)
{
int B = mod_sqrt(val);
for(std::vector<int>::iterator Prime = arr->begin(); *Prime <= B; ++Prime)
if (val % *Prime == 0)
{
return;
break;
}
++count;
arr->push_back (val);
}



Output:

time ./Large_Primes

15485867 1000001

real 0m3.939s
user 0m3.924s
sys 0m0.004s




EDIT 2!

Introducing prime sieve (Even faster!)

#include <iostream>
#include <vector>
#define MARK 10000001//ith prime

using std::vector;
using std::cout;
using std::endl;

/*
* Trying to implement a prime sieve. This is a work in progress
*/

int main()
{
const int ThisSize = MARK;
int counter = 0;

vector<bool> Sieve(ThisSize+2, true);
vector<unsigned> Helper(ThisSize+2, 3);

int s = 2;

bool checkingTime = false;

while (1)
{
unsigned w = 3;
int h = 0;

while (!checkingTime)
{
unsigned q = Helper.at(h);

for (unsigned Prod = w * q; Prod < (unsigned)Sieve.size() ; q+=2, Prod = w * q)
Sieve.at(Prod) = false;

Helper.at(h++) = q;

checkingTime = ((w > ((unsigned)Sieve.size() >> 1)) ? true : false);

w+=2;
}

for ( ;counter < ThisSize && s < (int)Sieve.size(); s += ((s > 2) ? 2 : 1))
if (Sieve.at(s))
{
++counter;
if (counter == ThisSize)
{
cout << s <<endl;
break;
}
}

if (counter == ThisSize)
break;
else
{
checkingTime = false;
Sieve.resize(Sieve.size() + ThisSize, true);
Helper.resize(Helper.size() + (ThisSize >> 1), 2);
}
}
return 0;
}


$ time ./Sieve
179424691

real 0m5.905s
user 0m5.364s
sys 0m0.488s

Enslaved
01-25-2013, 11:30 PM
Hehe nublet, project euler is easy, im on 140 answers, that was like A year ago , havent really been on since

Echo_
01-26-2013, 06:38 AM
In Clojure:

(defn prime? [n]
"Tests for primality using trial division."
(if (< n 2)
false
(empty? (remove #(not= (rem n %) 0) (take-while #(<= (* % %) n) (range 2 n))))))

(def primes (filter prime? (iterate inc 0)))

(println (take 10 primes)) ; Displays a sequence of the first 10 prime numbers
(println (nth primes 9)) ; Displays the 10th prime number

Plus this one caches the results already computed for later use, I <3 lazy sequences.

CynicRus
01-26-2013, 04:33 PM
Hm. Mine version


#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

int main()
{
clock_t start = clock();

const int AIM = 1000000;

int startSize = AIM;
int addSize = AIM;

vector<bool> nums(startSize);
vector<int> primeNums(AIM);

int foundPrimes = 0;

for (int i = 2; i < startSize; i++)
nums[i] = true;

bool addition = false;
int adder = 0;
while (true)
{
if (addition)
{
nums.resize(nums.size() + addSize, true);

for (int i = 0; i < foundPrimes; i++)
{
int cur_num = primeNums[i];
if ((addSize + ((nums.size() - addSize) % cur_num)) < cur_num)
continue;
for (int j = ((nums.size() - addSize) / cur_num) * cur_num; j < nums.size(); j += cur_num)
nums[j] = false;
}
}
else
addition = true;


int iter;
if (foundPrimes == 0)
iter = 2;
else
iter = primeNums[foundPrimes - 1] + 2;

for ( ; iter < nums.size(); iter++)
{
if (nums[iter])
{
primeNums[foundPrimes] = iter;
foundPrimes++;
if (foundPrimes == AIM)
break;
for (int j = iter + iter; j < nums.size(); j += iter)
nums[j] = false;
}
else
continue;

}
if (foundPrimes == AIM)
break;
}

cout << "Last prime: " << primeNums[AIM -1];

clock_t end = clock();
cout << "\n----------------" << endl;
cout << "Time: " << double(end - start) / CLOCKS_PER_SEC << " sec" << endl;
return 0;
}


Output:


Last prime: 15485863
----------------
Time: 4.331 sec


But if you show each found the number - it will be a bit slower.

Recursive
02-01-2013, 02:41 PM
Damm CynicRus is that prime sieve?

*Updated First post!*

Don't know why the c++ version of this code is not working:

#!/usr/bin/env python
import time

def GetPrimes2(n):

Sieve = [1 for g in xrange(0, n)]

for q in xrange (3, n, 2):
k = q
for y in xrange(k*k, n, k << 1):
Sieve[y] = 0

return Sieve



start = time.clock()

d = 1000000
Primes = GetPrimes2(d)

count = 1 #This is for 2

for x in range (3, d, 2):
if Primes[x]:
count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"



#include <iostream>
#include <ctime>
#define MAXPRIMES 1000000

typedef unsigned int uint;

int* GetPrimes(uint);

using std::cout;
using std::endl;

int main()
{
clock_t Starttime = clock();

const int W = MAXPRIMES;

int* Primes = GetPrimes(W);

int count = 1;//The number 2

for (int A = 3; A < W; A+=2)
if (Primes[A])
count++;

clock_t Endtime = clock() - Starttime;
cout << "\nFound " << count << " primes in " << (double) Endtime/CLOCKS_PER_SEC << " Seconds!\n\n";
return 0;
}



/*:::::::::::::::::::::::::::::::::::::::::::
:::::::*Optimized sieve function::::::::::::
::::::::::::::::::::::::::::::::::::::::::::*/
int* GetPrimes(uint AmtPrime)
{
int* Sieve = new int[AmtPrime];

for (uint i = 0; i < AmtPrime; ++i) Sieve[i] = 1;

for (uint w = 3; w < AmtPrime; w+=2)
for (uint q = w*w; q < AmtPrime; q = q + (w*2))
Sieve[q] = 0;

return Sieve;
}

CynicRus
02-21-2013, 05:27 AM
Apparently example incorrectly converted to C + +. Try to compile it with using ShedSkin and see what the problem is.