GitHub - chuggafan/Prime-Search: Testing primality of 2^MAXINT-1 I made this code in my spare time, if anyone wants to help me on it they may
It tests if 2^maxINT-1 is prime, i plan on adding more numbers eventually, but i made this program for one purpose and the ammount of work i put into it i thought made it a bit interesting[DOUBLEPOST=1458918986,1458907328][/DOUBLEPOST]I'm also thinking of posting regular updates here, so atm i'ved added more functionality, but you guys can also always make suggestions for what i should do! even with my little C# expierence, i know people that can do alot more, so request away!
2^maxINT-1, 500 million didgets, good luck, also, it now tests mersanne primes going down from maxInt, there's more options on the TODO i have to add
2^74,207,281 − 1 Current largest known prime is that, this is approximately 2^2140062866 times bigger than that, so it's going to take a long time to calculate.
thank you captain obvious, it's 500 million didgets long supposedly, i have it so that you can stop and start the program and it'll continue at the last checked number, i thought of that
? no, i'm using a brute force method, you can submit a pull request for me to look at on the github implementing this though, the code's all there
The issue with brute force is that you have to test division by every single integer below root(2^maxInt-1) which since it is so large will take forever. Doing this method you calculate S_(2^maxInt-3) using the recursion relation in the image (a huge number) and try dividing it by 2^maxInt-1, I don't know the language you are implementing the program in so wouldn't know how to implement this properly.
That doesn't help at all, btw, implement it in any language in full and i can translate it, i already only brute force using specifically prime numbers, so it's calculating a prime number, modulating the other number, then doing this again, and if the number that's modulating the larger number square is greater than the larger number, the larger number is prime (I tested this, this is true)
rough python pseudocode s0 = 4 p = 2**31-1 #prime we are checking Mp for mp = 2**p-1 #prime we are checking s = s0 for i in range(1, p-2): #might need to be p-1 here can't decide if this will loop one too few times sNew = (s**2)-2 s = sNew if 's/mp mod mp = 0': mp is prime else mp not prime I don't quite follow this
Yhea, i'm sorry, basically i'm taking y, which is gaurenteed prime, and taking the large number (h) and doing h mod y, then i make y the next prime number, after this i check if y^2 >= h, if it is, h is prime will implement this later, i think i understand it now, the sole problem of the program development is that to actually TEST the thing i need to sidestep debugging in VS and build outside as it throws an error, but otherwise, thanks
so you would start y=2, find h mod 2 = 1 ? where is the next y from for the iteration? 3? The issue I see here is that you essentially have to find all primes up to root(2^maxInt-1) via this method which is essentially impossible as the only way to guarantee this is to brute force division for each possible candidate for these lower primes. Hence using the proven method I suggested which is the fastest known method for calculating if it is prime. (although you still have to do approx 2^maxInt computations to reach the S_k and test it's divisibility) and I don't know if it is possible to be sufficiently accurate to do this with the size of the numbers involved (required S_k is larger in digits than prime you are attempting to check and I don't know how well code will handle that)
