- 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?)
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)
- 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)
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.