Randomly select a prime number

[danBarker]

I was wondering if they was an easy way to select a prime number at random. For example, rather than having a rather large array of prime numbers between the set I want, if I could have a random that just found them efficiantly.

I was thinkig about having the random select a number and then check if it is prime but because they isnt really that many prime numbers I dont think this is efficiant.

Any help would be fantastic, thanks.

[jsmith]

If primality tests were cheap, encryption/security would be unachievable.

Randomly generate an N, then brute force find the Nth prime number.

[adikid89]

Well.. you could for example you rand() function... somewhat like this:

while(true) {
int r = rand();
if(r==isPrime()) return r;
}

although it will probably be more cpu expensive than your array example, which is space inefficient but has a constant access...
What you could do.. is check all the prime numbers brute-force like, save them in a file for reusage, then load them in an array for quick acces to them. That might be the best solution..

[m4ster r0shi]

Check this out, I made it a while ago for a friend, I think you might find this useful. It has two operating modes, one that is fast but memory consuming and one that is slow but less memory consuming. Hope it helps! :)

#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

class RandomPrimeGenerator
{
      public:
      RandomPrimeGenerator(){mode=NONE; srand(time(0));}
      ~RandomPrimeGenerator(){}

      void init_fast(unsigned int _max_number);
      void init_cheap(unsigned int _max_prime_count);

      unsigned int get();
      
      private:
      unsigned int max_number;
      unsigned int max_prime_count;
      enum {NONE=0,FAST=1,CHEAP=2} mode;
      vector<unsigned int> prime_list;
      void find_primes();
};

void RandomPrimeGenerator::find_primes()
{
     prime_list.clear();
     prime_list.push_back(2);
     
     int i,j;
     unsigned int size=prime_list.size();
     bool is_prime;
     unsigned int cur_prime;
     for (i=3; max_number==0||i<=max_number; i+=2)
     {
         is_prime=true;
         for (j=0; j<size; j++)
         {
             cur_prime=prime_list[j];
             if (i<cur_prime*cur_prime) break;
             
             if (i%cur_prime==0) {is_prime=false; break;}
         }
         if (is_prime)
         {
            prime_list.push_back(i);
            size++;
            if (max_prime_count!=0&&size==max_prime_count) break;
         }
     }
}

void RandomPrimeGenerator::init_fast(unsigned int _max_number)
{
     max_number=_max_number;
     max_prime_count=0;
     mode=FAST;
     find_primes();
}

void RandomPrimeGenerator::init_cheap(unsigned int _max_prime_count)
{
     max_prime_count=_max_prime_count;
     max_number=0;
     mode=CHEAP;
     prime_list.clear();
}

unsigned int RandomPrimeGenerator::get()
{
     if (mode==NONE)
     {
        cerr << "random prime generator not initialized!...\n";
        return 1;
     }
     
     if (mode==FAST)
     {
        unsigned int size=prime_list.size();
        unsigned int index=int(0.5+(size-1)*(rand()/double(RAND_MAX)));
        return prime_list[index];
     }
     
     if (mode==CHEAP)
     {
        unsigned int index=int(0.5+(max_prime_count-1)*(rand()/double(RAND_MAX)));
        find_primes();
        return prime_list[index];
        prime_list.clear();             
     }     
}

int main()
{
    RandomPrimeGenerator rpg; //LOL
    int i;
    
    cout << "initializing fast way...\n";
    rpg.init_fast(1000000); //prime numbers up to 1000000
    
    cout << "getting random primes fast!\n";
    for (i=0; i<10; i++)
    {
        cout << rpg.get() << endl;
    }
    
    cout << "initializing cheap way...\n";
    rpg.init_cheap(75000); //first 75000 prime numbers
    
    cout << "getting random primes cheap!\n";
    for (i=0; i<10; i++)
    {
        cout << rpg.get() << endl;
    }
    
    system("pause");
    return 0;
}

[danBarker]

Thanks people. The replies really helped out. Once again thanks a lot!