Prime functions

[ayu]

Since we are working with a lot of prime numbers at uni at the moment, me and a friend are testing out a bunch of algorithms to sort out all the prime numbers in a certain length. Here is one I made just now, I'll add my friends if she creates one, and I'll add everything else we come up with as well ^^

The reason it's in a function is because I'm writing all the algorithms in the same program, and I want to separate it a bit.

Code: Select all

#include <iostream>

using namespace std;

void prime_one();

int main()
{
	prime_one();

	return 0;
}

void prime_one()
{
	const int MAX = 1000;
	bool prim;

	for(int i = 2; i <= MAX; ++i)
	{
		prim = true;

		for(int j = 2; j <= i && prim == true; ++j)
		{
			if(j < i && i % j == 0)
				prim = false;
		}

		if(prim == true)
			cout << i << " is a prime number\n";
		else
			cout << i << " is NOT a prime number\n";
	}
}

[DNR]

you have a girl friend?!

DNR

[ayu]

you have a girl friend?!

DNR

What's that? ^^


EDIT: testing prime algorithms... how romantic

[DNR]

right.

testing prime algorithms... how romantic

Thats so you, perhaps today - try not to be so much, 'you'.

This is your chance

DNR

[ayu]

Well, first of all, I would never be any less "me" then I am, just to flirt, and also, shes like twice my age .... ^^ (she's old enough to be my mother)


Anyway, if anyone has any other functions or something to add, feel free to =)

[Nerdz]

We had benchmark with prime number algorithm... it's not mine but it's the algo of the winner... cheer

Code: Select all

    bool MillerRabin(DWORD prime)
    {
       DWORD totalWitness = 3;
       DWORD randomWitness[] = {2, 7, 61};
       DWORD primeMinusOne = prime - 1;
       DWORD oddMultiplier;
       DWORD bitLength;
       DWORD i, j;
       DWORD result;

       oddMultiplier = primeMinusOne;
       bitLength = 0;
       while(!(oddMultiplier & 1))
       {
          oddMultiplier >>= 1;
          bitLength++;
       }

       for(i = 0; i < totalWitness; i++)
       {
          result = ExpModDWORD(randomWitness[i], oddMultiplier, prime);
          if(result == 1)
             continue; // maybe prime

          if(result == primeMinusOne)
             continue; // maybe prime

          for(j = 1; j <= bitLength; j++)
          {
             result = ExpModDWORD(result, 2, prime);

             if(result == primeMinusOne)
                break; // maybe prime
          }

          if(result != primeMinusOne)
             return(false); // COMPOSITE
       }

       return(true); // PRIME
    }

    DWORD ExpModDWORD(DWORD value, DWORD exp, DWORD mod)
    {
       ULONGLONG ullResult = 1;
       ULONGLONG ullValue = value;

       while(exp)
       {
          if(exp & 1)
          {
             ullResult *= ullValue;
             ullResult %= mod;
          }

          ullValue *= ullValue;
          ullValue %= mod;

          exp >>= 1;
       }

       return((DWORD) ullResult);
    }