fork(1) download
copy 
  1. // prime numbers
  2.  
  3. package main
  4.  
  5. import (
  6.     "fmt"
  7. )
  8.  
  9. // list of primes less than n:
  10. // sieve of eratosthenes
  11. func primes(n int) (ps []int) {
  12.     sieve := make([]bool, n)
  13.     for i := 2; i < n; i++ {
  14.         if !(sieve[i]) {
  15.             ps = append(ps, i)
  16.             for  j := i * i; j < n; j += i {
  17.                 sieve[j] = true
  18.             }
  19.         }
  20.     }
  21.     return ps
  22. }
  23.  
  24. // true if n is prime, else false:
  25. // trial division via 2,3,5-wheel
  26. func isPrime(n int) (bool) {
  27. 	wheel := [11]int{1,2,2,4,2,4,2,4,6,2,6}
  28. 	w := 0
  29. 	f := 2
  30. 	for f*f <= n {
  31. 		if n % f == 0 { return false }
  32. 		f += wheel[w]
  33. 		w += 1
  34. 		if w == 11 { w = 3 }
  35. 	}
  36. 	return true
  37. }
  38.  
  39. // greatest common divisor of x and y:
  40. // via euclid's algorithm
  41. func gcd(x int, y int) (int) {
  42. 	for y != 0 {
  43. 		x, y = y, x % y
  44. 	}
  45. 	return x
  46. }
  47.  
  48. // absolute value of x
  49. func abs(x int) (int) {
  50. 	if x < 0 {
  51. 		return -1 * x
  52. 	}
  53. 	return x
  54. }
  55.  
  56. // list of prime factors of n:
  57. // trial division via 2,3,5-wheel
  58. // to 1000 followed by pollard rho
  59. func factors(n int) (fs []int) {
  60.     wheel := [11]int{1,2,2,4,2,4,2,4,6,2,6}
  61.     w := 0 // wheel pointer
  62.     f := 2 // current trial factor
  63.     for f*f <= n && f < 1000 {
  64.         for n % f == 0 {
  65.             fs = append(fs, f)
  66.             n /= f
  67.         }
  68.         f += wheel[w]; w += 1
  69.         if w == 11 { w = 3 }
  70.     }
  71.     if n == 1 { return fs }
  72.     h := 1 // hare
  73.     t := 1 // turtle
  74.     g := 1 // greatest common divisor
  75.     c := 1 // random number parameter
  76.     for !(isPrime(n)) {
  77.         for g == 1 {
  78.             h = (h*h+c) % n // the hare runs
  79.             h = (h*h+c) % n // twice as fast
  80.             t = (t*t+c) % n // as the tortoise
  81.             g = gcd(abs(t-h), n)
  82.         }
  83.         if isPrime(g) {
  84.             for n % g == 0 {
  85.                 fs = append(fs, g)
  86.                 n /= g
  87.             }
  88.         }
  89.         h, t, g, c = 1, 1, 1, c+1
  90.     }
  91.     fs = append(fs, n)
  92.     return fs
  93. }
  94.  
  95. func main() {
  96.     fmt.Println(primes(100))
  97.     fmt.Println(isPrime(997))
  98.     fmt.Println(isPrime(13290059))
  99.     fmt.Println(factors(13290059))
  100. }
Success #stdin #stdout 0s 789504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[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]
true
false
[3119 4261]
https://ideone.com/qxLQ0D
language:
Go (go 1.12.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!