# Prime Numbers in Discrete Mathematics

**Overview :**

An integer p>1 is called a prime number, or prime if the only positive divisors of p are 1 and p. An integer q>1 that is not prime is called composite.

**Example –**

The integers 2,3,5,7 and 11 are prime numbers, and the integers 4,6,8, and 9 are composite.

Attention reader! Don’t stop learning now. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in **GATE Test Series Course**.

Learn all **GATE CS concepts with Free Live Classes** on our youtube channel.

**Theorem-1:**

An integer p>1 is prime if and only if for all integers a and b, p divides ab implies either p divides a or p divides b.

**Example – **

Consider the integer 12.Now 12 divides 120 = 30 x 4 but 12|30 and 12|4.Hence,12 is not prime.

**Theorem-2 :**

Every integer n>=2 has a prime factor.

**Theorem-3 : **

If n is a composite integer, then n has a prime factor not exceeding √n.

**Example-1 :**

Determine which of the following integers are prime?

a) 293 b) 9823

**Solution –**

- We first find all primes p such that p
^{2}< = 293.These primes are 2,3,5,7,11,13 and 17.Now, none of these primes divide 293. Hence, 293 is a prime. - We consider primes p such that p2< = 9823.These primes are 2,3,5,7,11,13,17, etc. None of 2,3,5,7 can divide 9823. However,11 divides 9823.Hence, 9823 is not a prime.

**Example-2 :**

Let n be a positive integer such that n^{2}-1 is prime. Then n =?

**Solution – **

We can write, n^{2}-1 = (n-1)(n^{2}+n+1). Because n^{3}-1 is prime, either n-1 = 1 or n^{2}+n+1 = 1.Now n>=1, So n^{2}+n+1 > 1,i.e., n^{2}+n+1 != 1.Thus, we must have n-1 = 1.This implies that n=2.

**Example-3 :**

Let p be a prime integer such that gcd(a, p^{3})=p and gcd(b,p^{4})=p. Find gcd(ab,p^{7}).

**Solution – **

By the given condition, gcd(a,p^{3})=p. Therefore, p | a. Also, p^{2}|a.(For if p^{2}| a, then gcd (a,p^{3})>=p^{2}>p, which is a contradiction.) Now a can be written as a product of prime powers. Because p|a and p^{2}| a, it follows that p appears as a factor in the prime factorization of a, but p^{k}, where k>=2, does not appear in that prime factorization. Similarly ,gcd(b,p^{4})=p implies that p|b and p^{2}|b. As before, it follows that p appears as a factor in the prime factorization of a, but p^{k}, where k>=2, does not appear in that prime factorization. It now follows that p^{2}|ab and p^{3}|ab. Hence, gcd(b,p^{7}) = p^{2} .

**Primality Test Algorithm :**

for i: [2,N-1] if i divides N return "Composite" return "Prime"

**Example –**

Let’s take an example and makes the algorithm more efficient, 36=

1×36 |

2×18 |

3×12 |

(a=4)x(b=9) |

6×6 |

9×4 (repeated) |

12×3 (repeated) |

18×2 (repeated) |

36×1 (repeated) |

Take the inputs of a and b until, a<=b a . b = N a . N/a = N

**Modified algorithm :**

for i : [2,√n] if i divides N return "Composite" return "Prime"

## C++

`// C++ program to check primality of a number` `#include <bits/stdc++.h>` `using` `namespace` `std;` `bool` `is_prime(` `int` `n){` ` ` `for` `(` `int` `i = 2; i * i <= n; i++){` ` ` `if` `(n % i == 0){` ` ` `return` `false` `;` ` ` `//if the number is composite or not prime.` ` ` `}` ` ` `}` ` ` `return` `true` `;` ` ` `// number is prime.` `}` `int` `main() {` ` ` `int` `n;` ` ` `cin >> n;` ` ` `cout << is_prime(n) ? ` `"prime"` `: ` `"composite"` `;` ` ` `return` `0;` `}` |

## Java

`// Java program to check primality of a number` `/*package whatever //do not write package name here */` `import` `java.util.*;` `class` `prime{` ` ` `public` `Boolean is_prime(` `int` `n){` ` ` `for` `(` `int` `i = ` `2` `; i * i <= n; i++){` ` ` `if` `(n % i == ` `0` `){` ` ` `return` `false` `;` ` ` `//if the number is composite or not prime.` ` ` `}` ` ` `}` ` ` `return` `true` `;` ` ` `// number is prime.` ` ` `}` `}` `class` `GFG {` ` ` `public` `static` `void` `main (String[] args) {` ` ` `Scanner sc = ` `new` `Scanner(System.in);` ` ` `int` `n = sc.nextInt();` ` ` `prime ob = ` `new` `prime();` ` ` `System.out.println(ob.is_prime(n) ? ` `"Prime"` `: ` `"Composite"` `);` ` ` `}` `}` |

## Python3

`# Python program to check primality of a number` `import` `math` `def` `is_prime(n):` ` ` `for` `i ` `in` `range` `(` `2` `, ` `int` `(math.sqrt(n))):` ` ` `if` `(n ` `%` `i ` `=` `=` `0` `):` ` ` `return` `False` ` ` `# if the number is composite or not prime.` ` ` `return` `True` ` ` `# number is prime.` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `n ` `=` `int` `(` `input` `())` ` ` `if` `is_prime(n):` ` ` `print` `(` `"prime"` `)` ` ` `else` `:` ` ` `print` `(` `"composite"` `)` ` ` `# This code is contributed by rakeshsahni` |

## Javascript

`<script>` `// JavaScript program to check primality of a number` `function` `is_prime(n)` `{` ` ` `for` `(` `var` `i = 2; i * i <= n; i++)` ` ` `{` ` ` `if` `(n % i == 0){` ` ` `return` `false` `;` ` ` ` ` `// if the number is composite or not prime.` ` ` `}` ` ` `}` ` ` `return` `true` `;` ` ` `// number is prime.` `}` ` ` `var` `n;` ` ` `document.write(is_prime(n) ? ` `"prime"` `: ` `"composite"` `);` ` ` `// This code is contributed by shivanisinghss2110` `</script>` |

**Algorithm to find prime numbers :**

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

Algorithm Sieve of Eratosthenes is input: an integer n > 1. output : all prime numbers from 2 through n. let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true. for i = 2, 3, 4, ..., not exceeding √n do if A[i] is true for j = i^{2}, i^{2}+i, i^{2}+2i, i^{2}+3i, ..., not exceeding n do A[j] := false return all i such that A[i] is true.