How to check whether a number is prime or not?

Question

The problem is to check whether a number is prime or not . The number may contain milion digit. The process must be very efficient.

Answer 1

A prime number is only divisible by 1 and itself. One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime. One need not actually calculate the square root; once one sees that the quotients exceed the divisors, one can stop. This is known as trial division; it is the simplest primality test and it quickly becomes impractical for testing large integers because the number of possible factors grows exponentially as the number of digits in the number-to-be-tested increases.

Answer 2

In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. There exists an infinitude of prime numbers, as demonstrated by Euclid in about 300 B.C.. The first 30 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, and 113 .

The property of being a prime is called primality, and the word prime is also used as an adjective. Since 2 is the only even prime number, the term odd prime refers to all prime numbers greater than 2.

A primality test algorithm is an algorithm which tests a number for primality, i.e. whether the number is a prime number.

AKS primality test
Fermat primality test
Lucas-Lehmer test
Solovay-Strassen primality test
Miller-Rabin primality test
A probable prime is an integer which, by virtue of having passed a certain test, is considered to be probably prime. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes.

In 2002, Indian scientists at IIT Kanpur discovered a new deterministic algorithm known as the AKS algorithm. The amount of time that this algorithm takes to check whether a number N is prime depends on a polynomial function of the number of digits of N (i.e. of the logarithm of N).

for more information pl. visit:
http://en.wikipedia.org/wiki/Primality_test

Answer 3

On modern computers, with the most efficient known modern algorithms, testing the primality of an arbitrary 200-digit number is trivial, but a 1000-digit number is a serious challenge and 2000 digits is in effect quite impracticable. Trial division up to the square root is the simplest but least efficient algorithm known.

Record-breaking Mersenne primes have a special form which allows the use of a peculiarly efficient special test.

Answer 4

Prime numbers lie at the core of some of the oldest and most perplexing questions in mathematics. Evenly divisible only by themselves and 1, they are the building blocks of integers.

Although there are infinitely many primes, they are also relatively scarce and rather haphazardly scattered among the integers.

Indeed, of the first 25 billion whole numbers, only 1,091,987,405—or about 4 percent—are primes, and the proportion of primes decreases as the numbers get bigger.

The absence of any readily discernible pattern in their distribution makes identifying primes a tricky proposition.

Is 687,532,127 a prime? There's no way to tell simply by looking.

Clearly, the number isn't evenly divisible by two, nor by any other even number. Is it divisible by 3? 5? 7? By 26,203? In fact, 687,532,127 has no divisors other than one and itself, so it's a prime.

This process of elimination by trial division is the idea behind the prime-detecting sieve of Eratosthenes, named for a Greek mathematician who lived in the third century B.C. The sieve of Eratosthenes represents a systematic way of checking whether a number is a prime by dividing into the given number all smaller primes, starting with two and going up to the square root of the target number. If none of the integers divides evenly into the given number, the target is a prime. In the case of huge numbers, however, trial division is both tedious and time-consuming.

Even so, the need to undertake such primal analysis has mushroomed because of the increasing importance of cryptography. One widely used cryptographic scheme is based on the notion that, whereas it's relatively easy to multiply together large primes, it's considerably more difficult to factor the resulting number and retrieve the original primes. Yet that operation is just the one required for decoding the encrypted messages. This scheme requires a ready-to-use supply of large primes, so it has encouraged mathematicians and computer scientists to seek increasingly efficient ways of identifying prime numbers.

Now, a team from the Indian Institute of Technology (IIT) in Kanpur, India, has devised a novel approach for detecting primes. The new technique solves a long-standing problem in number theory and computer science, providing a long-sought improvement in the theoretical efficiency of prime-detecting algorithms.

For the rest of the article:
http://www.sciencenews.org/articles/20021026/bob9.asp

Answer 5

A prime number is a number which has only two factors viz '1' and the number itself.
Or
A prime number is a number which is divisible only by '1' and the number itself
For example 5 is a prime number Why???????
The factors of 5 are 1 and 5 only
Similarly 2 is also a prime number because 2 has only two factors namely 1 and 2

Answer 6

Okay check the below algorithm, which is efficient.

Input is n
output is prime or not

Start
{
for k<-2 to root(n)
{
if n mod k=0 then {n is not prime stop}
else {continue}
}
print(n is prime)
}

the explanation for the above


The reason that you only need to go up
to the square root of n is that if n has some factor f, then that
means that the number

n/f

is also a factor of n. It turns out that either f or n/f has to be
less than or equal to the square root of n. So if you don't find any
factors from 2 up to the square root of n, then you won't find any
factors from the square root of n.

example Okay, suppose you are trying to see if the number 309733 is prime.
Well, it turns out that 2741 is a factor of that number, but you'll
never find this factor because it is bigger than the square root of
309733. But no fear! Because the corresponding factor

309733/2741 = 113

is less than the square root of 309733. And you will find that one,
so your algorithm will conclude (correctly) that 309733 is not prime.

Answer 7

Factoring is sort of the opposite of multiplying, but more creative than division. To factor a number what we want to do is find numbers to multiply and get it, for example we can factor 15 as 3x5, and we can factor 12 as 2x6 or 3x4. Some numbers can be factored many different ways, but others can't be factored very many ways at all. All numbers can be factored as themselves times 1, but that's not very interesting.

Answer 8

firstly find the square root of given number then check with the numbers below the square root if it is divisible any of the number between 1 and its square root it is not prime otherwise it is prime.

Answer 9

a prime number is one which is divisible only by itself & by 1.. division of it by any other number gives remainder..
for example , if you take 11, its only divisible by 1 and 11. so 11 is a prime number...

Answer 10

Go to https://mit.academia.edu/ConstantineAdraktasPrimeNumbers and you have the answer on whether a number is prime or not