/sci/ - Science, Technology, Engineering, and Mathematics

Prime test Anonymous 22/02/17(Thu)19:25 No. 18131 ID: f85074

File 164512235712.jpg - (3.32KB , 119x122 , download.jpg )

Today one of my recurring dream characters named Jennifer Zemblini gave me a prime number test that correctly validated the first few hundred prime numbers in under 3 seconds using C# code I wrote to validate her primality test!

I wanted to share the primality test with you all now.

It uses only simple division, addition and subtraction. And three variables called n, A and B.

n is defined as the number being tested for primeness. A0 is n-2 and B0 is 2.

Then apply this procedure: Divide A by B, if it is not a clean division, meaning there is a remainder, add one to B and subtract one from A, and repeat this step until B approaches one-half of n.

If A can never divide evenly into B then n is prime.

For example with n=9, which is not prime: A = 9-2. B =2. 7/2 is not even. 6/3 does evenly divide with result 2. And 3 is a factor of 9 also.

But for a prime like 13: 11/2... 10/3... 9/4... 8/5... 7/6... None of these divide cleanly with no remainder, therefore 13 is prime.

I made a C# code in 19 lines based on this primality test and it correctly worked for every number I tested and it was very fast too. Let me know if anybody can find an example that proves this primality test wrong and invalid. Appreciated.

If this becomes the biggest discovery in math history then I require you name the primality test the "French Celestial girlfriend prime number test." :p

Anonymous 22/02/20(Sun)13:49 No. 18138 ID: 7e46a7

File 164536138648.jpg - (337.79KB , 899x1203 , Medicine Buddha palace.jpg )

Are you positive Jennifer Zemblini is French though?

Anyway I just glanced at the post and found it somewhat reminding of Euclid Algorithm.

>Let me know if anybody can find an example that proves this primality test wrong and invalid.
How far have you tested?
Have you tried into a proof of correctness of the algo instead?

Anonymous 22/02/21(Mon)05:13 No. 18140 ID: bf7eac

Even assuming it is correct, the algorithm is actually pretty bad. It takes O(n) operations to find out if a number is prime. The fastest primality test by trial division finishes in only O(sqrt(n)) operations:

 bool is_prime(int n){ if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; int m = (int)sqrt(n); for (int i = 3; i <= m; i += 2) if (n % i == 0) return false; return true; } 

I still need to figure out whether it's correct. Will post back.

Anonymous 22/02/21(Mon)05:14 No. 18141 ID: bf7eac

>>18140
Oh, that's great. Fucking bbcode.

Anonymous 22/02/21(Mon)05:31 No. 18142 ID: bf7eac

Ah, got it.

n is divisible by m if and only if n + m * k is also divisible by m, where k is any integer value. This is deducible from the definition of division in integer arithmetic:

(Reminder: the dividend is the left-hand side operand for / and %, while the the divisor is the right-hand side.)

quotient * divisor + remainder = dividend
(dividend = n + m * k, divisor = m, remainder = 0)
quotient * m + 0 = n + m * k
quotient * m + 0 = n + m * k
(quotient - k) * m + 0 = n
quotient2 * m + 0 = n
quotient is still zero when dividend = n, thus n % m == (n + m * k) % m for any integer k.

In other words, testing whether (n - a) % a == 0 is equivalent to testing n % a == 0, and testing all the way up to n / 2 is valid as long as n / 2 >= sqrt(n), so the test is actually invalid for n < 4 and could return a false positive. It just so happens that both 2 and 3 are prime, so there's no room for false positives in that range.

Anonymous 22/02/21(Mon)05:33 No. 18143 ID: bf7eac

>>18142
>quotient is still zero when dividend = n, thus n % m == (n + m * k) % m for any integer k.
This is an error. I meant to say that the remainder is still zero.

Anonymous 22/06/19(Sun)13:11 No. 18281 ID: e5a2d8

I want to clarify that you don't need to sweap across the entire half of the number. If there are no such A and B before B is greater than sqrt(n). There won't be any at all.
And what you did is just a fancy way to do Euclid primality test by checking the first sqrt(n) numbers if any divide n. Since you are checking if B divides A which is none but n-B
Since for all B, B divides itself
So B divides the sum of n-B and B = n
So you're back with the normal primality test, maybe even worse cause you are wasting time computing n-B.
Your Jennifer is retarded.

Anonymous 23/07/26(Wed)00:04 No. 18683 ID: cbe355

Your primality test is 100% right and there is no exception to it. The only problem is that it's not only inefficient (it has an asymptotic complexity of O(n)) but it is basically testing the divisibility of n by any number in the range (2,n/2).

[Return] [Entire Thread] [Last 50 posts]