Where it runs
1. The problem
A video is 1920 wide and 1080 tall. A person calls that format 16:9. To get there, you divide both numbers by the biggest number that divides both of them with nothing left over. For 1920 and 1080 that number is 120: 1920 / 120 = 16, 1080 / 120 = 9.
How do you find it? The slow way is to try candidates from the smaller number down and check whether each one divides both numbers. For small numbers that is quick. For the pair 1000000007 : 500000000 you would check up to 500 million candidates.
A similar question comes up when two repeating events have to coincide. One job runs every 4 seconds, another every 6. After how many seconds do they fire at the same moment? This needs the opposite number: the smallest number that both divide into. For 4 and 6 it is 12.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedsieve(30)| 1 | 2 | 3 | 4 | 5 | 6 |
| 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 |
Find every prime up to 30. Start with all numbers from 2 standing; crossing out multiples will leave only the primes.
Bars: one per number from 2 to 49. Every bar starts high; a number found to be composite drops to zero, and the primes stay standing.
One operation is one division or one crossing out. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n√n)O(n log log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- reduce a fraction to lowest terms
- list all primes up to n
- answer modulo 1e9+7
- when do two repeating intervals line up again (LCM)
Looks similar, isn't
- Bit manipulation
Both work on the number itself. That page is about the individual bits.
- Hash set / map
A set of primes still has to be built somehow. A sieve is how you build it.
- Dynamic programming (1-D)
A formula answers at once where DP fills a table. Look for a closed form first.
- Prefix sums
Prefix sums answer over values that were stored. Here the answer comes from the numbers themselves.
GCD costs O(log of the smaller value). A sieve up to 1e7 is fine, but 1e9 is not.
On LeetCode
Problems that reduce numbers or strings to a common step, such as the GCD of an array, slopes between points or what two jugs can measure. Euclid's loop finds the GCD in O(log n), and the LCM follows from it.
Take the smallest and the largest number and return the lesson's gcd of the two.
A common divisor string exists only when str1 + str2 equals str2 + str1, and then its length is the gcd of the two lengths.
Count each card value and check that the gcd of all the counts is at least 2.
Two jugs can measure exactly the multiples of their gcd, up to their combined size.
Store each slope from a point as a pair reduced by the gcd, with one sign rule, so equal slopes give equal keys in the Map.