Prime number? - Page 2
Page 2 of 2 FirstFirst 12
Results 11 to 14 of 14

Thread: Prime number?

  1. #11
    Senior Member
    Join Date
    Feb 2002
    Posts
    170
    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
    Mankan

    \"The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise.\"
    - Edsger Dijkstra

  2. #12
    AntiOnline Senior Member souleman's Avatar
    Join Date
    Oct 2001
    Location
    Flint, MI
    Posts
    2,884
    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.
    \"Ignorance is bliss....
    but only for your enemy\"
    -- souleman

  3. #13
    Senior Member
    Join Date
    Oct 2001
    Posts
    677
    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.
    One Ring to rule them all, One Ring to find them.
    One Ring to bring them all and in the darkness bind them.
    (The Lord Of The Rings)
    http://www.bytekill.net

  4. #14
    Senior Member
    Join Date
    Oct 2001
    Posts
    677
    Code:
    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).
    One Ring to rule them all, One Ring to find them.
    One Ring to bring them all and in the darkness bind them.
    (The Lord Of The Rings)
    http://www.bytekill.net

Posting Permissions

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