Hi;

Is this what you are trying?

http://en.wikipedia.org/wiki/Fermat%27s … ion_method

There are lots of methods to factor numbers but none of them are very fast for large numbers. That method in the link is a method discovered by Fermat. There is also trial division. Their are quadratic sieve methods, wheel methods, elliptic curve methods etc. Except for trial division and Fermats method they are all complicated.

Where did you get it?

That is what I can not give you. The fermat's method on the Wikipedia page is well known, the one you are asking about looks like it but I am not sure. It could be a modification of the standard fermats method, there are a couple of improvements. But I do not recognize it.

Hi;

Are you doing some calculations with that algorithm? Supposing that method works. It still is very inefficient. I think the one on Wikipedia is a better way to do it.

X on all the square number between 2 - y

Are you saying divide X by all the squares between 2 and y? Or all the primes form 2 - y? Which is just trial division.

The quickest way to know whether a number is prime aside from using the sieve of eratosthenes method is:
1. Find the square root of the number (e.g. 179, square root of 179 is approximately 13)
2. Try to divide 179 by any of the prime numbers up to 13 in this case, so use 7, 11 and 13 only.
    Definitely if the number ends in 5, then it's composite, and if the sum of the digits of the given number is a multiple of 3, then it's divisible by three
3. Since in my example, 7, 11 and 13 does not divide 179, then 179 is prime.

Note, all even numbers greater than 2 are composite numbers, and only numbers ending in 1, 3, 7 or 9 are possible prime, but mostly not.

Make sure to always check whether it's divisible by 3 first up to the nearest square root of the given number.

Hi y'all

To just find out whether a number n is prime or not, one of the fastest methods is as follows:

   In the following b is any base: 2,3,4,5,... preferably a prime.  I usually use 2 and do the
calculations on Maple.

   Calculate  b^(n-1) mod n.  If this turns out to be 1, then the chances are overwhelming
that it is prime.  The exceptions are called Carmichael numbers and they are they are few
and far between.  The first two are  651 and 1105. 
   41041 is the eleventh Carmichael number.  The factors of a psuedoprime have to be "just right"
for them to produce a 1 in this calculation. 

   Google Carmichael Number to see several articles about this.  Some of these articles should tell
how to determine whether of not you have a Carmichael number.

If n is a Carmichael number and gcd(n,b)>1 then the mod will not be 1.
There are only 8241 Carmichael numbers less than 10^12.  That's 8.241*10^(-7) %.

So this mod test is a quick test to determine primality with a high degree of probability. 
You might also Google the Miller-Rabin test for primality.  (There's a Wiki article.)

Primality is much easier and faster to determine than doing a factorization.