Prime factor $>250000$ for $1002004008016032$ I need to find a prime factor, $p$, of $1002004008016032$ such that $p \gt 250000$. Now this is a very large number and I know it would be stupid of me to factorize such a large number into its prime factors . Any help how I can solve this ?
 A: $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+xy^{n-2}+y^{n-1})$
Taking $x=10^3,y=2$, we get 
$1002004008016032=x^5+x^4y+x^3y^2+x^2y^3+xy^4+y^5=\frac{x^6-y^6}{x-y}$
Also, 
$\frac{x^6-y^6}{x-y} = (x+y)(x^2+xy+y^2)(x^2-xy+y^2)$
=$1002\times1002004\times998004 = 1002\times16\times250501\times249501$
Hence, the prime number , $p\gt250000$ is $250501$
A: The OP was looking for any help. If all you have as an aid is access to the Python programming language, you can code this:
L = 1002004008016032
b = 250001

while True:
    r = L % b
    if r == 0:
        print(b)
        break
    b = b + 1

for n in range(2,int(b**.5)+1):
    if b % n == 0:
        print(b, 'is not a prime')
        raise SystemExit

print(b, 'is a prime')
raise SystemExit

giving the output
250501
250501 is a prime

ANS: $250501$
If it turned out that $250501$ was not a prime, you would have to edit the while loop, changing it to
while True:
    r = L % b
    if r == 0 and b != 250501:
        print(b)
        break
    b = b + 1

and then rerun the program to get the next factor candidate.
It is possible that many reruns would be required to find the answer using this technique, but the code can also be easily modified with a one-run requirement.
