Favourite prime generator?

[Whovian]

As the name asks, what's your favourite prime generator you've written? Mine would probably be very similar to another one, but without those segmentation faults:

#include <iostream>
#include <vector>
#include <cmath>

int main()
{
    std::vector<int>primes;
    primes.push_back(2);
    for (int i = 2;;i++)
    {
        bool isprime = true;
        for (int j = 0;primes[j]<=std::sqrt(i);j++)
        {
            if (i % primes[j] == 0)
            {
                isprime = false;
                break;
            }
        }
        if (isprime)
        {
            std::cout << i << std::endl;
            primes.push_back(i);
        }
    }
}

[Albatross]

Mine is probably this one. O:)

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <math.h>

using namespace std;
int size;
int* primes;
bool checkprimeness(int i)
{
	for (int j = 0; j < size; j++) 
		if (i % primes[j] == 0) return false;
	return true;
}

void main()
{
    int max;
    printf("Enter your number: ");
    cin >> max;
	system("cls");
	
    if (max < 2) {
	printf("What the fortran do you take me for?\nThere are no positive primes here!\n");
		exit(0);
    }
	else {
		primes = (int*)malloc(4*max);
		size = 0;
		primes[size] = 2, size++;
	}
	
	int i;
    for (i = 2; i < max+1; i++) {
		if (checkprimeness(i))
			primes[size] = i, size++; 
	}
	
	cout << "\n";
    for (i = 0; i < size; i++) 
		cout << primes[i] << "\n";
	
    system("pause");
}

Warning: Do not run this program. It has a memory leak that needs fixing first.

-Albatross

[BlackSheep]

A sieve:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int max;
	std::cin>>max;
	bool *sieve = new bool[max];
	for(size_t i = 0; i < max+1; ++i)
	{
		sieve[i] = true;
	}
	sieve[0] = false;
	sieve[1] = false;
	
	for(size_t i = 0; i < max+1; ++i)
	{
		if(sieve[i] == true)
		{
			for(size_t w = i*2; w < max+1; w+=i)
			{
				sieve[w] = false;
			}
		}
	}

	std::string answer[2] = {" "," not "};

	for(size_t i = 0; i < max+1; ++i)
	{
		std::cout<<i<<" is"<<answer[sieve[i]?0:1]<<"a prime."<<std::endl;
	}
	
	std::getchar();
	std::getchar();
        delete[] sieve;
    return 0;
}

EDIT: Memory leak.
Also, Whovian, you should probably allocate memory for your vector at the beginning like Albatross, since re-sizing is pretty costly. You'll use more memory, but get better performance.

[Whovian]

@albatross True. \Edits a bit

EDIT: I meant @BlackSheep, sorry

[Albatross]

O_o

I did not think anyone would ever learn anything from that prime number generator, even if through another person referencing it.

I deliberately wrote it to be dripping with pure unadulterated evil meant to make competent C++ professors faint in their chairs.

Life is full of surprises. *shrug* :)

-Albatross

[BlackSheep]

Are you kidding me Albatross? That's the most beautiful program I've ever seen. I like how you modularized checkprimeness, and the system calls are extremely useful for portability. And everyone knows malloc is much safer than new. Who would trust their memory allocation to the compiler to figure out? That's just silly.

[Catfish2]

Edit: Whooops. Is this a joke thread? I see some sources are... peculiar.

So I moved my own code here, to keep the thread "clean": http://pastebin.com/1SzLA2z6

[S G H]

Mine is something like this:

bool IsPrimeNumber(const int &Number)
{
    Network_AskOperator("Is Number Prime?",Number, "*Your Email Address Here*");
    return Network_WaitReply("*Your Email Address Here*") == 1;
}

Just kidding, never had to create a prime generator before.

[BlackSheep]

We could use Java:

import java.math.prime
import java.math.number
import java.input
import java.output

public class IsPrime
{
        public static void main()
        {
        Input input = new Input();
	Number num = new Number();
        Prime prime = new Prime();
        Output output = new Output();
        num.value = input.get();
	if(prime.isprime(num))
		{
			output.print(num + " is prime.");
		}
        else
		{
			output.print(num + " is not prime.");
		}
        }
}

[Catfish2]

I am genuinely interested in that Java program, but I can't compile it.

[chrisname]

I didn't know how to write a prime number generator, so I decided to write a prime number generator generator instead. Then I didn't know how to do that, so I wrote a prime number generator generator generator: http://codepad.org/oHth65wk

[edit] Notice how a 3 kiB file generates a 2 kiB file which generates a 480 byte file (which is the complete opposite of what metaprogramming is supposed to do).

Example:

$ g++ -o pggg pggg.cpp
$ ./pggg
$ g++ -o pgg pgg.cpp
$ ./pgg 100
$ g++ -o pg pg.cpp
$ ./pg
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

[Catfish2]

\\\\
\\\\\
_\\\\\
~~~~~~~
|    |
|  __|/  *       |
| | ||           \O
| | ||   *     | /|_
| | ||~        \/
| | ||      ___/      *  /~~~/
| |_|| *                /---/
|    |\      *     *   /~~~/
|    |                    *

[chrisname]

I just had mine print every prime up to 2,147,483,647 (INT_MAX) and it finished in just under 41 minutes. Is that good or bad?

[rollie]

sieve of atkin (faster then esost-whatever):

void load_primes(std::set<unsigned int> & _primes, unsigned int _limit = 1000000)
{
	double sqlim = std::sqrt((double)_limit);
	unsigned int * primes = new unsigned int [_limit + 1];
	memset(primes, 0, sizeof(int) * (_limit + 1));

	for (int x = 1; x <= sqlim; x++)
	{
		for (int y = 1; y <= sqlim; y++)
		{
			unsigned int n = 4*x*x + y*y;
			if (n <= _limit && (n%12 == 1 || n%12 == 5))
			{
				primes[n] ^= 1;
			}

			n = 3*x*x + y*y;
			if (n <= _limit && n%12 == 7)
			{
				primes[n] ^= 1;
			}

			n = 3*x*x - y*y;
			if (x > y && n <= _limit && n%12 == 11)
			{
				primes[n] ^= 1;
			}				
		}
	}

	// Eliminate composites
	for (int n = 5; n < sqlim; n++)
	{
		if (primes[n])
		{
			unsigned int k = n*n;
			while (k <= _limit)
			{
				primes[k] = 0;
				k += n*n;
			}
		}
	}

	primes[2] = primes[3] = primes[5] = 1;

	for (unsigned int i = 1; i <= _limit; i++)
	{
		if (primes[i])
		{
			_primes.insert(i);
		}
	}

	delete primes;
}

[rollie]

And as long as we're at it, miller-rabin test for primality

todo: add random num gen at todo, allow k as parameter

Also, it uses a typedef 'UInt4' which is a typedef of the ttmath uint, with one modification, an inclusion of a powmod function which I've included. Note that you can't always just take the power then modulus for large exponents without requiring prohibitively large numbers. You can make it work with anything though, just templatize as appropriate, and make PowMod another templated function instead of a method of uint4.

(this is all from my project euler solving tools)

bool is_prime(UInt4 _num)
{
	const int k = 40;
	
	if (_num < 2)
	{
		return false;
	}

	static std::set<unsigned int> primes;
	if (primes.size() == 0)
	{
		load_primes(primes, 300);
	}

	for (auto itr = primes.begin(); itr != primes.end(); itr++)
	{
		if (_num == *itr)
		{
			return true;			
		}

		if (_num % *itr == 0)
		{
			return false;
		}
	}

	UInt4 d = _num - 1;
	int s = 0;
	while((d & 1) == 0)
	{
		d = d / 2;
		s++;
	}

	for (int i = 0; i < k; i++)
	{
		UInt4 a((_num / 47 + 15) / 3 + 29);   // TODO: random
		UInt4 x = a;
		if(x.PowMod(d, _num) == 1)
		{
			std::cout << "Carry taking " << a << "^" << d << std::endl;
			exit(1);
		}

		if (x == 1 || x == _num - 1)
		{
			continue;
		}

		bool bMaybePrime = false;
		for (int r = 1; r <= s; r++)
		{
			x = x*x % _num;

			if (x == 1)
			{
				break; // composite
			}
			else if(x == _num - 1)
			{
				bMaybePrime = true;
				break;	// next loop
			}
		}

		if (!bMaybePrime)
		{
			return false;
		}
	}

	return true;
}

PowMod:

/*!
		mod power this = (this ^ pow) % m
		binary algorithm (r-to-l)

		return values:
		0 - ok
		1 - carry
		2 - incorrect argument (0^0)
	*/
	uint PowMod(UInt<value_size> pow, UInt<value_size> mod)
	{
		if(pow.IsZero() && IsZero())
		// we don't define zero^zero
		return 2;
				
		UInt<value_size> remainder;
		UInt<value_size> x = 1;
		
		uint c = 0;
		
		while (pow != 0)
		{
			remainder = (pow & 1 == 1);
			pow /= 2;
			if (remainder != 0)
			{
				c += x.Mul(*this);
				x = x % mod;								
			}

			c += Mul(*this);
			*this = *this % mod;		
		}
		
		*this = x;
		return (c==0)? 0 : 1;
	}

[chrisname]

I didn't even write my prime generator, I wrote a program to write a program to do it for me.

[LB]

import static java.lang.Math.*;
#include <iostream>

struct PrimeNumberGenerator
{
    static void main(int argc, String[] argv)
    {
    PrimeLoop:
        for(;;)
        {
            long n = (long)(random()*0b_1010101010101010101010101010101010101010101010101010101010101010l);
            for(unsigned long i = 0; i < (long)sqrt(n); ++i)
            {
                if(n%i == 0)
                {
                    continue PrimeLoop;
                }
            }
            std::cout << n << std::endl;
        }
    }
}

Good luck finding a compiler.

[Catfish2]

I just had mine print every prime up to 2,147,483,647 (INT_MAX) and it finished in just under 41 minutes. Is that good or bad?

I was about to say you can probably improve it, by disregarding numbers divisible by primes under 100, thereby reducing used space and also the time to build it (which is where much of those 41 minutes was spent).

But then rollie came along!