Question: Maple help me please

March 09 2014 c4meleon 15
Maple
2

Hi,
can you please help me solve that?
I want to write maple procedure that checks if a number is prime or not and I need to do it so that it doesn`t take forever to give an answer.
I wrote a procedure that works good with small numbers but when I put bigger numbers eg.9999971 it is taking far too long (5min) to get the answer, I tried to modify it and I think I find out something that could be modified to make it more efficient, like for example in the line:   for j from 2 to n-1 do     (I changed it to: ) for j from 2 to n-1  by n do    - it tooks 9.953 second to get the answer   (or I changed it to: ) for j from 2 to (n-1)/2  do   - it tooks 262.062 second I also tried many things and I always get an answer after long time excepte when I changed the line to for j from 2 to (n-1)/n  do   - it tooks 0 second but I didn't find any explanation why should I devide it by n as j from 2 to ((n-1)/n) = 1-(1/n) which is less than 2 as it make no sence....
But it still not efficient enough, because if for example I use the maple command isprime,then I got the result in less than 1 second.
In the program I used other procedure that I think will make it quicker which is a floor function procedure. please see bellow :  

> flr:=proc(a,b)

      local n:

      n:=0:

      while a>=b*(n+1) do

         n:=n+1:

     od:

       n;

   end:

 


> Isprime:=proc(n)        

         local j, p:      

         p:=true:               

         if n=2 then

            p:=true;       

        else

             for j from 2 to n-1 do 

                  if (n/j-flr(n,j))=0 then

                       p:=false:

                  fi:

              od:

         fi:

     p:

     end:

 

>zeit:=time():

Isprime(9999971); 

time()-zeit,`second`;

                                                                   true

                                                                    309.558, second

 

Please reply and thank you in advance

Please Wait...