Prime number?

[Mankan]

Ah, The Sieve of Eratosthenes. I wrote some on it a while back if anyone is interested:
http://www.cshrp.net/content.aspx?showID=612

[souleman]

Rewandythal> also do b+2 instead of b++. If 2 is eleminated, then no even number can possible go into a.

garathjax> I don't remember exactly which test the ARP test is....and don't have time to look it up right now. I just wanted to warn you that certain tests only work for certain primes. Certain numbers (2^3-1 for example) follow set rules, but that doesnt mean that all primes follow the same rules. Some just make it quick to find. There is a project called the GIMP (I believe) which is working on determining extreamly large prime numbers. The last one was something like 4million digits. Their goal is to find the first prime number greater then 10million digits.

[Rewandythal]

b=2, b+2 takes is straight to 4, missing out 3, I'd have to go from b=1, which would return 1 and would *appear* therefore not to be prime (since a / 1 would be a whole number).

I could of course start at 3, but it'd then miss out the important /2 stage, so 4, for example, would be misreported as prime.

[Rewandythal]

int IsPrime(int a)
{
	int b;
	int c;
    if( (a div 2) == (a / 2))
    {
        c = 1;
    }
	for(b = 3;b < sqrt(a); b + 2)
	{ 
		if( (a div b) == (a / b))
		{
			c = 1;
		}
	}
	return c;
}

// Returns 0 if prime, 1 if not

This solves the problem, by checking for divisible by 2 first, then starting at 3, incrementing in 2's (all the odd numbers).