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