Freshers Interviews: Prime Numbers!

Prime Numbers:

Prime Numbers are those natural numbers divisible only by 1 and themselves.These are building blocks of natural number arithmetic.

Some interesting things about prime numbers.

1)Any Natural number can be expressed uniquely as product of powers of distinct primes.This procedure of finding the powers of primes contained in a number is called Prime Factorization.

2)There are infinitely many prime numbers.

3)If a number N is not prime, then it should have a factor less than sqrt(N).Hence the procedure to test whether a number is prime or not is of complexity O(sqrt(N)).

Prime Twin Pairs

One of the first things noticeable about tables of primes is that there are many instances of pairs of prime numbers with the form n and n + 2.

Examples are 11 and 13, 17 and 19, 29 and 31, 101 and 103, 881 and 883, and so on.

These are sometimes called prime twin pairs. No one has ever determined if this is an interesting property of numbers or just a curious coincidence.
The instances of pairs of prime numbers decrease for ever larger numbers.

Palindromic Primes

One of the more curious prime number puzzles that mathematicians have examined is the occurrence of palindromic primes.

A palindrome is a word or phrase that reads the same forward or backward. Some examples of palindromic primes are 101, 131, 151, 181, 313, 353, 727, 757, 787, 79997, 91019, 1818181, 7878787, 7272727, and 3535353. There is an infinite number of palindromic primes.

Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for generating a list of all prime numbers up to a given integer N. It does this using

O (N)

space .

We begin by making a table of integers 2 to N.We find the smallest integer i, that is not crossed out,print i and cross out i, 2i , 3i, .........When i >sqrt(N) the algorithm terminates and further numbers which aren't crossed out printed.

Q1)Suggest ways to improve it further.

Solution:The improvement in terms of space requirements that can be done is accomodating only odd numbers as 2 is the only even prime.
considering time complexity, we can limit the strike off to multiples of prime P greater than P*P ,hence reducing the number of numbers traversed.

What is the complexity of this algorithm?

Solution:Nlog(N)

Q2)In the above mentioned facts about primes ,the second one claims that there are infinite number of primes.Prove it

Solution:Let there be finite number of primes say K.let the primes be P1,P2,....,Pk.
now consider the number N=P1*P2*P3*P4....*Pk + 1.
clearly none of the above k primes divide N.Hence N is also a prime contradicting our initial assumption.

Q3)Show that (N^4 + 4N) is a prime number if and only if N=1. (really simple)

Solution:let f(N)=N^4 + 4N.
f(1)=5 which is prime.
for N greater than 2 we can write f(N)=N(N^3+4) as product of 2 numbers both of which are greater than 1.Hence it is composite.
Hence proved.

Relative Primes

When gcd(m, n) = 1, the integers m and n have no prime factors in
common and we say that they’re relatively prime.

Euler's Phi Function

Euler's Phi function, also known as the totient function, is a function that, for a given positive integer

N

, calculates the number of positive integers smaller than or equal to

N

that are relative prime to

N

. (Note that except when

N = 1

, only integers strictly smaller than

N

are counted.

Mathematical Definition

$\phi(N) = \Big|\, \{ i ~~|~~ 1\leq i\leq N ~\land~ \gcd(i,N)=1 \} \Big|$
where | | indicates the cardinality of the set.

Features of Euler's Phi Function

1) φ(p) = p - 1

for

p

prime, because all numbers smaller than

p

are relatively prime to

p

2) φ(N)

is even for all

N > 2

, because if

k

is relatively prime to

N

, so is

N - k

, and they are distinct.

3) It is a multiplicative function in the number-theoretic sense:

φ(M N) = φ(M)φ(N)

whenever

gcd(M, N) = 1

.

4) $\phi(p^k) = p^k-p^{k-1} = p^{k-1}(p-1) = p^k\left(1-\frac{1}{p}\right)$ , because among the integers from

1

p k

, the integers not relatively prime to

p k

are precisely those divisible by

p

, and there are

p k - 1

of them.

5)Let $N = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}$ be the prime factorisation of

N

. That is, the

p i

s are distinct primes and each

α i

is a positive integer. Then $\phi(N) = (p_1^{\alpha_1}-p_1^{\alpha_1-1})\cdots(p_r^{\alpha_r}-p_r^{\alpha_r-1}) = N \left( 1 - \frac{1}{p_1} \right)\left( 1 - \frac{1}{p_2} \right) \cdots\left( 1 - \frac{1}{p_r} \right)$

If you have perhaps gone through the above facts,you can try solving the below mentioned
programming problems which test the basics

http://acm.uva.es/p/v101/10168.html

http://acm.uva.es/p/v106/10699.html

http://acm.uva.es/p/v107/10789.html

http://acm.uva.es/p/v108/10852.html

http://acm.uva.es/p/v108/10871.html

http://acm.uva.es/p/v109/10924.html

http://acm.uva.es/p/v1/160.html

http://acm.uva.es/p/v2/294.html

http://acm.uva.es/p/v4/406.html

http://acm.uva.es/p/v5/516.html

http://acm.uva.es/p/v5/543.html

http://acm.uva.es/p/v5/583.html

Remember that the solutions to these problems should be efficient in terms of time and space complexities.

post your valuable comments so that we can learn better through discussion.

Solutions to all the above problems shall be posted soon!!

2 comments:

UnknownSeptember 19, 2007 10:14 PM
Thanks for the article. Your comments/questions re. twin primes and the sieve touch on topics discussed in detail at www.primestructure.com. Here you'll see how structure can be added to the sieve, and numerous logical consequences of doing so.
AnonymousJune 07, 2010 11:50 PM
very useful and valueable information about prime nos... great work..
please post the solution to these problems too...

Top Menu

Prime Numbers!

2 comments: