70 lines
1.6 KiB
Go
70 lines
1.6 KiB
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
func sieve(limit int) []int {
|
|
var primes []int
|
|
c := make([]bool, limit + 1) // composite = true
|
|
// no need to process even numbers
|
|
p := 3
|
|
p2 := p * p
|
|
for p2 <= limit {
|
|
for i := p2; i <= limit; i += 2 * p {
|
|
c[i] = true
|
|
}
|
|
for ok := true; ok; ok = c[p] {
|
|
p += 2
|
|
}
|
|
p2 = p * p
|
|
}
|
|
for i := 3; i <= limit; i += 2 {
|
|
if !c[i] {
|
|
primes = append(primes, i)
|
|
}
|
|
}
|
|
return primes
|
|
}
|
|
|
|
// finds the period of the reciprocal of n
|
|
func findPeriod(n int) int {
|
|
r := 1
|
|
for i := 1; i <= n + 1; i++ {
|
|
r = (10 * r) % n
|
|
}
|
|
rr := r
|
|
period := 0
|
|
for ok := true; ok; ok = r != rr {
|
|
r = (10 * r) % n
|
|
period++
|
|
}
|
|
return period
|
|
}
|
|
|
|
func main() {
|
|
primes := sieve(64000)
|
|
var longPrimes []int
|
|
for _, prime := range primes {
|
|
if findPeriod(prime) == prime - 1 {
|
|
longPrimes = append(longPrimes, prime)
|
|
}
|
|
}
|
|
numbers := []int{500, 1000, 2000, 4000, 8000, 16000, 32000, 64000}
|
|
index := 0
|
|
count := 0
|
|
totals := make([]int, len(numbers))
|
|
for _, longPrime := range longPrimes {
|
|
if longPrime > numbers[index] {
|
|
totals[index] = count
|
|
index++
|
|
}
|
|
count++
|
|
}
|
|
totals[len(numbers)-1] = count
|
|
fmt.Println("The long primes up to", numbers[0], "are: ")
|
|
fmt.Println(longPrimes[:totals[0]])
|
|
|
|
fmt.Println("\nThe number of long primes up to: ")
|
|
for i, total := range totals {
|
|
fmt.Printf(" %5d is %d\n", numbers[i], total)
|
|
}
|
|
}
|