Number Theory

Date: Jan 28, 2021
Conducted By: Khushi and Kushagra

Agenda

• Checking whether a number is prime or not
  • Naive approach
  • O(sqrt(N)) approach
• Prime factorisation in O(sqrt(N))
• Sieve of Eratosthenes
  • Illustrating the concept
  • Answering multiple queries
  • Prime factorisation using smallest prime factor (spf)
  • Further optimisations

Resources

• Checking whether a no. is prime
• Prime factorisation in O(sqrt(N))
• Sieve and spf

Further Reading

• Basic Number Theory Every Programmer Should Know… - CodeChef
• Basic Number Theory-2 - HackerEarth
• Prime Numbers Factorization and Euler Function - TopCoder
• [Tutorial] Math note — linear sieve - Codeforces

Practice Problems

• DSA Learning Series - Mathematics in CP - CodeChef
• CodeChef Prepare
  • Prime Numbers, divisibility of numbers
  • Sieve of Eratosthenes
• Edu Contest #3