Instantly share code, notes, and snippets.

pknowledge/primalitytest.py

Created June 9, 2020 21:10
Show Gist options
• Save pknowledge/edad3fd2b42998f31689a8342913d0e7 to your computer and use it in GitHub Desktop.
Number Theory for Competitive Programming with Python - Compare Primality Test in O(n) vs O(root(n)) https://youtu.be/4UZufg54dFc
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # Prime numbers two factors 1 , Number Itself # Approach One O(n) # Aprroach Two: Base Case + Hint: O(1) -> O(root(N)) from math import * def approach1(n): divcnt = 0 for i in range(1,n+1): # [1,n] if n%i == 0: divcnt+=1 print(divcnt) if divcnt == 2: return True else: return False def approach2(n): if n == 0 or n == 1: # O(1) return False if n == 2 or n == 3:# O(1) return True if n%2 == 0 or n%3 == 0:# O(1) return False for i in range(5,int(sqrt(n))+1): # [1,root n] if n%i == 0 or n%(i+2) == 0: return False return True # approach2 more effiecient t = int(input()) while t: n = int(input()) #print(approach1(n)) print(approach2(n)) t = t -1