From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,f856693efe5e5bdb
X-Google-Attributes: gid103376,public
From: mfb@mbunix.mitre.org (Michael F Brenner)
Subject: Re: Prime Number Algorithm Needed
Date: 1997/11/22
Message-ID: <657i4v$p6h@top.mitre.org>#1/1
X-Deja-AN: 291638725
References: <6548v3$ocm$1@news1.bu.edu>
Organization: none
Newsgroups: comp.lang.ada
Date: 1997-11-22T00:00:00+00:00
List-Id: <comp.lang.ada>


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 :)