How to check if a number is prime without trial division

Level: High School
Thread starter Loismustdie
Start date Oct 6, 2006
Tags

Numbers Prime Prime numbers

Join the discussion

Registration is free. Start your own thread to ask a follow-up.

1 reply · 3K views

Loismustdie

Thread starter
Oct 6, 2006

I don't know if this is the right place to put this but it seemed close enough. Anyway I wanted to know if there was anyway to check whether a number is prime or not without doing a lot of division.

Physics news on Phys.org

Ultrathin materials could make quantum light circuits programmable
Spin rephasing helps quantum memories store single-photon states longer for future networks
Discovery confirms rare, switchable electrical property in widely used electronics material

Discussion

CRGreathouse

Science Advisor

Homework Helper

Oct 6, 2006

Sure, lots of ways. Here's one of the easier:
http://primes.utm.edu/prove/prove2_3.html

How to check if a number is prime without trial division

Discussion

Similar threads

Undergrad The worst case for trial division factorisation of n?

How to Check if a Number is Prime in Python?

Undergrad Is Trial Division Primality Check Considered in Polynomial Time?

High School How do you quickly check if a large number is prime?