Prime Count Problem

Getting Help Code Review
1

I am trying to create a function that returns me the total count of the prime numbers, but the problem I am running into is that it is not working for few cases like 3, or 4. Can you please tell me where am I making mistake?
n = 10

    func primeNumber(n int) int { 

    var totalNumberOfPrimes int
    
    for i := 2; i <= n/2; i++ {
        
        if n%i == 0 {
            fmt.Printf("The value is the not prime %v \n", i)
            
        }
        totalNumberOfPrimes++
    }
    
    return totalNumberOfPrimes
}
1 Like
2

The solution is to implement the sieve of Erastothenes.

The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

Wikipedia: Sieve of Eratosthenes

3 Likes
4

Here is an old code snippet of mine to help you find the more simple solution.
https://play.golang.org/p/Lm2DawMbzlu

6

The OP asked for:

Your code is not correct. Your code returns 35 for CountPrimes(0, 100). OEIS, an authoritative source, says 25.

package main

import (
	"fmt"
	"math"
)

// The On-Line Encyclopedia of Integer Sequences (OEIS)
// A000040 The prime numbers
// https://oeis.org/A000040
var A000040 = []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,
}

func main() {
	fmt.Println("robinbraemer:")
	// println(CountPrimes(0, 100))
	count := CountPrimes(0, 100)
	primes := Primes(0, 100)
	fmt.Println(count, primes)

	fmt.Println("OEIS:")
	count = len(A000040)
	primes = A000040
	fmt.Println(count, primes)
}

func ForPrimes(min, max int, fn func(p int) bool) {
	for i := min; i <= max; i++ {
		if IsPrime(i) && !fn(i) {
			return
		}
	}
}
func IsPrime(n int) bool {
	testUntil := int(math.Sqrt(float64(n)))
	for i := 2; i < testUntil; i++ {
		if math.Mod(float64(n), float64(i)) == 0 {
			return false
		}
	}
	return true
}

func Primes(min, max int) (primes []int) {
	ForPrimes(min, max, func(p int) bool {
		primes = append(primes, p)
		return true
	})
	return
}
func CountPrimes(min, max int) (count int) {
	ForPrimes(min, max, func(p int) bool {
		count++
		return true
	})
	return
}

robinbraemer:
35 [0 1 2 3 4 5 6 7 8 9 11 13 15 17 19 23 25 29 31 35 37 41 43 47 49 53 59 61 67 71 73 79 83 89 97]
OEIS:
25 [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]
7

Blockquote Here is an old code snippet of mine to help you find the more simple solution.
https://play.golang.org/p/Lm2DawMbzlu

This is wrong code: it counts x*x as prime. For example, it will return 25 as being prime. You should replace for i := 2; i < testUntil; i++ { with i <= testUntil

8

After your change, the code is still wrong.