AlgoScope

Primality Test

Try each divisor up to the square root. No hit means prime.

Mathematics, algorithm, beginner
Trying 2. It does not divide 97.2031425364758697i
Trying 2. It does not divide 97.2031425364758697i

Number Theory Basics: Is 97 prime?

Decision, step 2 of 10

97 mod 2 = 1, not zero. 2 is not a factor.

How number theory basics works

Cost

Best
O(1)
Average
O(sqrt(n))
Worst
O(sqrt(n))
Space
O(1)

Before this

Variants

  • Trial DivisionDeterministic
  • Miller-RabinProbabilistic

Leads to

Topics that need this one first.

Taught by the same lesson

Number Theory Basics covers these too, in the same run.