is there a formula, function or way to determine if a.....

Post Reply New Topic

number is prime or not, without having to try different numbers as factors inductively?? if there is, what is it? and if there isn't, do you think we're close to discovering a function, formula or program that can identify prime numbers?? so far i have a theory, or should i say conjecture.

conjecture: 2 to the power of a prime number then subtract one. 2^prime number then subtract one. i tried it with numbers 2,3,5,7, and it worked. but it lacks sufficient evidence to classify it as a theory

Any number(x) is prime if it cant be divided by any number smaller or equal to(x/2).

Not really a formula but it makes you check half of the original numbers.

There are plenty of examples of calculating wether a number is prime on a programming language online(c,c++,java...) so you may want to look into those examples if you are interested, see how they do their calculations and how they work.

Yes, we already have ways of talking about primeness without talking about factors. For example, a number k + 2 is prime if and only if a certain set of 14 equations in 26 variables (depending on k) has a natural number solution.

However, the practical answer is "no". If you're serious about checking whether a number is prime, and the number doesn't happen to fall into a "nice" category of primes, you're going to have to talk about factors (at least indirectly).

I don't think this will ever change. In my opinion, the computational problem can't ever escape the fact that the definition of primes talks about "factors".

You don't have to look for factors all the way up to x/2; if x is composite, then necessarily one of its prime factors is less than or equal to sqrt(x). But even this is a relatively slow method. Faster algorithms are usually based on the fact that if x is prime and a is any positive integer, then a^x-a is divisible by x. It is not necessarily true the other way around, although counterexamples can be rare (for example, 341 = 11x31 is the smallest composite x such that 2^x-2 is divisible by x), so a number of a's have to be tested. You can look up these things on wikipedia or mathworld.wolfram.com.

For mental calculations, trying out prime factors less than sqrt(x) is often the only feasible method, but sometimes one can apply some tricks to speed things up. If you can easily see that x is the sum of the squares of two relatively prime integers, then none of x's prime factors can be congruent to 3 (mod 4). Also if you can spot that x is the difference between two squares that are not consecutive, then you immediately have a factorization by a*2-b^2 = (a-b)(a+b).

Prime numbers of the form 2^p-1 are called Mersenne primes. p is called a Mersenne exponent. It doesn't work for all prime numbers.
http://en.wikipedia.org/wiki/Mersenne_prime
http://en.wikipedia.org/wiki/Chinese_hypothesis
The first few Mersenne exponents are 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497...

Dividing by all the primes up to √x is the simplest method, but it is very slow, and for larger numbers it's best to use a different one. Most methods are quite complicated.
http://en.wikipedia.org/wiki/Prime_fact ... algorithms

RSA encryption is based on the difficulty of factoring large prime numbers.

There are algorithms that can determine if a number is prime but don't find the factors, and these are much faster.

i am only posting in this thread because it is a coincidence that yesterday i decided to write a program that checks if a number is prime, and also generates successive prime numbers (for no other reason than it was a simple fun exercise).
i can offer no new solution to checking whether astronomically large numbers are prime because i have thought hard about the relationships between prime numbers to try to find some sort of correlation, but i have not found any.
i have thought about "radial peppering of morphological geometric point sets" (my term) that may more rapidly deduce whether a number is prime, but that takes even more computational power to execute. nice ideas but impossible to test.

the program i wrote last night (not inspired by this thread but coincident with it) seems to be able to determine whether a very large number is prime in a short time, and i recorded a video of it's operation, but i was tired, and now i realize that is demonstrates very little, since every number i entered into it was rapidly found to be not prime, so i entered "29" into it to demonstrate that it could find primes, and there is nothing amazing about that since 29 is a very small number.

so today i searched google for "very large prime numbers" so i could test my program with very large prime numbers, but all i could find was lists of prime numbers with 17+ million digits which is ridiculous (and they must be represented in scientific notation which is only approximate).
i can not test "astronomically" large numbers because my computer only can handle up to 30 digit numbers.

i did find a list of numbers in wikipedia that were less than 30 digits, and i tested a few of them and it took 10-15 seconds to find that they were prime. i will record a video soon that shows that the program handling these numbers.

i am not going to waste my life trying to come up with an idea that can instantly calculate whether any possible number (no matter how large) is prime, because many better minds than mine have tried and failed. i do not think it can be done.

so here are 2 videos that i recorded. the first one is the "check prime" function, and the second one is the
generate primes" function.

i will not yet disclose the code because i am not finished thinking about the matter.


[youtube]http://www.youtube.com/watch?v=-aIxEdkiTcI&feature=c4-overview&list=UUpB1H594Ek2H_hWBxJ7ja7g[/youtube]

[youtube]http://www.youtube.com/watch?v=7z5Nv4dF4OY&feature=c4-overview&list=UUpB1H594Ek2H_hWBxJ7ja7g[/youtube]

The simplest way is just trying it. The problem is known to be solvable in polynomial time, but that's sometimes still too bad.

In cryptography, the Fermat test is used. It is fast, but it is never 100% accurate – there are "pseudo-primes" for which the tests holds but which are not prime. The compromise between the probability of failure and speed is acceptable for practical purposes.

For a survey, see http://en.wikipedia.org/wiki/Primality_test.

Edit: Also have a look at http://en.literateprograms.org/Miller-Rabin_primality_test_%28Python%29. It's a practical implementation of a variant of the Fermat test.