V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Linear Sieve

Generate primes while marking each composite exactly once by its smallest prime factor.

Core idea

Process integers in order. An unmarked value is prime; multiplying it and every earlier prime marks composites, but the loop stops when that prime divides the current value.

Read the visualization

The number grid distinguishes new primes from composites, while the prime list drives each product. The break point identifies the smallest prime factor responsible for a composite.

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

Initialize the prime list and smallest-prime-factor table through the limit.

1function linearSieve(n: number): { primes: number[]; spf: number[] } {
2 const isComp = new Array(n + 1).fill(false);
3 const spf = new Array(n + 1).fill(0);
4 const primes: number[] = [];
5 for (let i = 2; i <= n; i++) {
6 if (!isComp[i]) primes.push(i); // i rest → prime
7 for (const p of primes) {
8 if (i * p > n) break; // mark
9 isComp[i * p] = true; // mark i×p(mark one times)
10 spf[i * p] = p; // mark minimum prime factor mark p
11 if (i % p === 0) break; // p mark i mark minimum prime factor → mark
12 }
13 }
14 return { primes, spf };
15}
range1..30
confirmed prime0
1 / 13

Complexity and tradeoffs

Time: O(N). Space: O(N). The break rule prevents a composite from being produced by more than its smallest prime factor.

Invariant: Before advancing past i, every composite generated so far has been generated exactly once by its smallest prime factor.

Where it fits

The linear sieve produces primes and smallest prime factors together, enabling fast factorization and multiplicative-function tables over a bounded range.