1. ## Prime number finder

Made program that finds the ith prime number. I made it for projecteuler. 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:

C++ Code:
`/*Owner: Re_cursive *Date: 10/12/12*/#include <cstdlib>#include <cstdio>#include <cstring>#include <cmath>//function headersuint 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 primenessbool 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 valueuint* 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:

C++ Code:
`#include <cstdio>#include <vector>#include <cmath>#define MAX 1000001int 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);}`

Code:
```Output:

time ./Large_Primes

15485867 1000001

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

EDIT 2!

Introducing prime sieve (Even faster!)

C++ Code:
`#include <iostream>#include <vector>#define MARK 10000001//ith primeusing 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;}`

Code:
```\$ time ./Sieve
179424691

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

2. Hehe nublet, project euler is easy, im on 140 answers, that was like A year ago , havent really been on since

3. In Clojure:

LISP Code:
`(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.

4. Hm. Mine version
Code:
```#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

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

const int AIM = 1000000;

int startSize = AIM;

vector<bool> nums(startSize);

int foundPrimes = 0;

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

while (true)
{
{

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

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

for ( ; iter < nums.size(); iter++)
{
if (nums[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:
Code:
```Last prime: 15485863
----------------
Time: 4.331 sec```
But if you show each found the number - it will be a bit slower.

5. Damm @CynicRus is that prime sieve?

*Updated First post!*

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

python Code:
`#!/usr/bin/env pythonimport timedef 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 Sievestart = time.clock()d = 1000000Primes = GetPrimes2(d)count = 1 #This is for 2for x in range (3, d, 2):    if Primes[x]:        count+=1elapsed = (time.clock() - start)print "\nFound", count, "primes in", elapsed, "seconds!\n"`

C++ Code:
`#include <iostream>#include <ctime>#define MAXPRIMES 1000000typedef 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;}`

6. Apparently example incorrectly converted to C + +. Try to compile it with using ShedSkin and see what the problem is.