8000 find the prime numbers with eratosthenes method · developgo/algorithms_with_Go@f1f5222 · GitHub
[go: up one dir, main page]
Skip to content

Commit f1f5222

Browse files
danruseidanrusei
committed
find the prime numbers with eratosthenes method
1 parent 8e6397c commit f1f5222

File tree

5 files changed

+117
-1
lines changed

5 files changed

+117
-1
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,7 @@ WIP, the descriptions of the below `unsolved yet` problems can be found in the [
8686
- [] Modular multiplicative inverse
8787
- [] Primality Test | Set 2 (Fermat Method)
8888
- [] Euler’s Totient Function
89-
- [] Sieve of Eratosthenes
89+
- [x] [Sieve of Eratosthenes](https://github.com/danrusei/algorithms_with_Go/tree/main/numbers/eratosthenes)
9090
- [] Convex Hull
9191
- [] Basic and Extended Euclidean algorithms
9292
- [] Segmented Sieve

‎numbers/eratosthenes/README.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
# Sieve of Eratosthenes
2+
3+
Source: [GeeksforGeeks](https://www.geeksforgeeks.org/sieve-of-eratosthenes/amp/)
4+
Source: [Wikipedia - Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
5+
6+
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
7+
8+
## Example
9+
10+
> Input : n =10
11+
> Output : 2 3 5 7
12+
>
13+
> Input : n = 20
14+
> Output: 2 3 5 7 11 13 17 19
15+
16+
## Algorithm
17+
18+
A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself.
19+
20+
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
21+
22+
* Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
23+
* Initially, let p equal 2, the smallest prime number.
24+
* Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
25+
* Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
26+
* When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
27+
28+
The main idea here is that every value given to p will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5).
29+
30+
As a refinement, it is sufficient to mark the numbers **in step 3 starting from p * p**, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p2 is greater than n.
31+
32+
## Result
33+
34+
```bash
35+
$ go test -v
36+
=== RUN TestReverse
37+
=== RUN TestReverse/10_value
38+
=== RUN TestReverse/20_value
39+
=== RUN TestReverse/99_value
40+
--- PASS: TestReverse (0.00s)
41+
--- PASS: TestReverse/10_value (0.00s)
42+
--- PASS: TestReverse/20_value (0.00s)
43+
--- PASS: TestReverse/99_value (0.00s)
44+
PASS
45+
```

‎numbers/eratosthenes/primes.go

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package primes
2+
3+
func primes(num int) []int {
4+
numbers := make([]bool, num)
5+
6+
//create the slice of bools and mark initially all true
7+
//a value in numbers[i] will finally be false if i is Not a prime, else true.
8+
for i := 0; i < num; i++ {
9+
numbers[i] = true
10+
}
11+
12+
for p := 2; p*p < num; p++ {
13+
//if numbers[p] is not changed, then it is a prime
14+
// this selects only the alreade identified prime numbers
15+
if numbers[p] {
16+
// search for multiple of p, and mark them as false
17+
for i := p * p; i < num; i += p {
18+
numbers[i] = false
19+
}
20+
}
21+
}
22+
23+
//create the list that containts only the prime numbers
24+
primes := []int{}
25+
for i := 2; i < num; i++ {
26+
if numbers[i] {
27+
primes = append(primes, i)
28+
}
29+
}
30+
return primes
31+
}

‎numbers/eratosthenes/primes_test.go

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package primes
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func TestReverse(t *testing.T) {
9+
for _, tc := range testcases {
10+
t.Run(tc.name, func(t *testing.T) {
11+
result := primes(tc.num)
12+
if !reflect.DeepEqual(result, tc.expected) {
13+
t.Errorf("Expected: %d, got: %d", tc.expected, result)
14+
}
15+
})
16+
}
17+
}

‎numbers/eratosthenes/test_cases.go

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package primes
2+
3+
var testcases = []struct {
4+
name string
5+
num int
6+
expected []int
7+
}{
8+
{
9+
name: "10_value",
10+
num: 10,
11+
expected: []int{2, 3, 5, 7},
12+
},
13+
{
14+
name: "20_value",
15+
num: 20,
16+
expected: []int{2, 3, 5, 7, 11, 13, 17, 19},
17+
},
18+
{
19+
name: "99_value",
20+
num: 99,
21+
expected: []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97},
22+
},
23+
}

0 commit comments

Comments
 (0)
0