Main content
Computer science theory
Course: Computer science theory > Unit 2
Lesson 6: Primality test- Introduction
- Primality test challenge
- Trial division
- What is computer memory?
- Algorithmic efficiency
- Level 3: Challenge
- Sieve of Eratosthenes
- Level 4: Sieve of Eratosthenes
- Primality test with sieve
- Level 5: Trial division using sieve
- The prime number theorem
- Prime density spiral
- Prime Gaps
- Time space tradeoff
- Summary (what's next?)
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
Primality test challenge
How can a machine tell us if a number is prime? Created by Brit Cruise.
Want to join the conversation?
- What is the machine in the photo?(4 votes)
- I think it is an old type of calculator which was kind of similar to a mechanical abacus.(2 votes)
- why can't we add super computers together to get faster results?(2 votes)
- Correct, this is called parallel computing, but there are some things to be calculated that can't give output (due to overflow) even if we use every computer on the planet(3 votes)
Video transcript
Voiceover: We begin with
a very simple question. Or not a question, a challenge. We need to build a machine
which takes an input and that input is some integer X, and all that machine needs to do is output true or false. That is the first step. Now we will use the computer science tool to actually build this machine together. One of the questions
that we will be asking is two things, two
aspects to this machine. How much time that a clock, how much time does it
take to give the solution and how much space does it need? When I say space, I mean, for in the case of this
mechanical calculator physical space, how many rooms do we need to hold our machine? Or if we're using a computer, how much memory does it need? We will be returning to
this two ideas as we go.