Prime Number Algorithm Needed

Prime Number Algorithm Needed

[Thomas Dauria]

I am looking for a good prime number algorithm.  The
user would be entering a number and I would need to find
the next prime greater than or equal to this user
entered number.


Any help would be greatly appreciated.

tom

tdauria@bu.edu

Re: Prime Number Algorithm Needed

[Geert Bosch]

Thomas Dauria <tdauria@bu.edu> wrote:
   I am looking for a good prime number algorithm.  The
   user would be entering a number and I would need to find
   the next prime greater than or equal to this user
   entered number.

Actually now I think about it, this would be a really neat
simple exercise for somebody starting with an introductory 
course on programming.

Of course, if your goal is not learning the language, but rather 
finding those nasty prime numbers I would suggest using one of 
those fine prime number applications that already exist. With 
all the fuss about encryption lately, they are becoming 
increasingly popular. 

A good binary version for DOS, OS/2 and Linux is at 
   http://www.leo.org/pub/comp/platforms/pc/msdos/apps/maths/prime13.zip

Regards,
   Geert

Re: Prime Number Algorithm Needed

[Michael F Brenner]

Prime numbers are intricately related to Mathematical Group Theory.
If G is a finite Group with order (G) equal to a prime number
then G is a cyclic group. However, this implication is not two-way,
so we cannot depend on a loop like the following:
    G:=create_cyclic_group(PRIME);
    loop
         PRIME := PRIME + 1;
         loop               
            H := create_group (with_order => PRIME);
            if cyclic(H) then raise found_the_next_prime_number; end if;
            exit when no_more_groups_of_this_order;
         end loop;
     end loop;


However, we also have Fermat's Theorem that if N is a prime number
and I is any integer, then I**N is congruent to I modulo N. That can
lead to the following loop.

      N:=get_prime_number_from User;
      assert (prime (N));
      loop
         n:=n+1;
         exit when check_all_integers (against_prime_number => N);
       end loop;
       text_io.put_line ("the next prime is " & integer'image (N));

Either of these two ways gives you something to think about. So, Happy
Thinksgiving :)