Results 1 to 6 of 6

Thread: Prime number finder

  1. #1
    Join Date
    Dec 2011
    Location
    -bash
    Posts
    515
    Mentioned
    0 Post(s)
    Quoted
    27 Post(s)

    Default 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 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:

    C++ Code:
    #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);
    }

    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 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;
    }

    Code:
    $ time ./Sieve
    179424691
    
    real	0m5.905s
    user	0m5.364s
    sys	0m0.488s

  2. #2
    Join Date
    Jan 2012
    Location
    127.0.0.1
    Posts
    702
    Mentioned
    11 Post(s)
    Quoted
    76 Post(s)

    Default

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

  3. #3
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    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. #4
    Join Date
    May 2012
    Location
    Moscow, Russia
    Posts
    661
    Mentioned
    35 Post(s)
    Quoted
    102 Post(s)

    Default

    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; 
        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:
    Code:
    Last prime: 15485863
    ----------------
    Time: 4.331 sec
    But if you show each found the number - it will be a bit slower.
    Per aspera ad Astra!
    ----------------------------------------
    Slow and steady wins the race.

  5. #5
    Join Date
    Dec 2011
    Location
    -bash
    Posts
    515
    Mentioned
    0 Post(s)
    Quoted
    27 Post(s)

    Default

    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 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"



    C++ Code:
    #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;
    }

  6. #6
    Join Date
    May 2012
    Location
    Moscow, Russia
    Posts
    661
    Mentioned
    35 Post(s)
    Quoted
    102 Post(s)

    Default

    Apparently example incorrectly converted to C + +. Try to compile it with using ShedSkin and see what the problem is.
    Per aspera ad Astra!
    ----------------------------------------
    Slow and steady wins the race.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •