Re: Prime Number Algorithm Needed

[mfb@mbunix.mitre.org (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 :)