P03 素数统计(BF算法、埃筛法)

青旅半醒 2022-10-09 03:10 136阅读 0赞

> 质数(素数): 除了1和它本身，无法被其他数整除的数（0、1除外）。  
> 100以内的质数共有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

# 1、暴力算法 #

统计n以内的素数个数  
比如5要与 2、3、4求余；  
比如7要与 2、3、4、5、6求余；  
所以x要与\[2:x-1\]内的值进行求余; 也就是要和比自己小的数进行求余。

var total int
    func isPrime(x int) bool { 
    	for i := 2; i < x; i++ { 
    		total++
    		if x%i == 0 { 
    			return false
    		}
    	}
    	return true
    }
    func main() { 
    	var count int
    	for x := 2; x <= 20; x++ { 
    		if isPrime(x) { 
    			count++
    		}
    	}
    	fmt.Print("Prime inside of 20: ", count)
    	fmt.Println("遍历次数: ", total)
    }

> Prime inside of 20: 8  
> 遍历次数: 74

# 2、埃筛法 #

原理: 由两数相乘必是合数(非素数)，所以把由当前质子与其他数字相乘得到数标记为合数，遍历时跳过  
默认全部为素数，以质数2开始，找出由2作为因子的合数；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70]

var total int
    func PrimeCount(number int) (count int) { 
    	// 素数标记为false, 默认全是素数
    	var array = make([]bool, number+1)
    
    	for i := 2; i <= number; i++ { 
    		// 标记为合数(array[index]=true)跳过，只判断标记为false(素数)
    		if !array[i] {  // 找到质数(2)后, 与之后的2,3,4...进行相乘得到合数，进而标记
    			fmt.Printf("[*] 将素数%d及大于其的自然数相乘寻找合数，并且合数小于指定范围内：\n", i)
    			for j := i; i*j <= number; j++ {  // i不变，j在i的基础上自增
    				total++
    				fmt.Printf("%d * %d = %d, %d标为合数; ", i, j, i*j, i*j)
    				array[i*j] = true
    			}
    			count++
    		}
    	}
    	return
    }
    
    func main() { 
    	fmt.Println("PrimeCount inside of 20: ", PrimeCount(20))
    	fmt.Println("遍历次数: ", total)
    }

> 将素数2及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 2 \* 2 = 4, 4标为合数; 2 \* 3 = 6, 6标为合数; 2 \* 4 = 8, 8标为合数; 2 \* 5 = 10, 10标为合数; 2 \* 6 = 12, 12标为合数; 2 \* 7 = 14, 14标为合数; 2 \* 8 = 16, 16标为合数; 2 \* 9 = 18, 18标为合数; 2 \* 10 = 20, 20标为合数;  
> 将素数3及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 3 \* 3 = 9, 9标为合数; 3 \* 4 = 12, 12标为合数; 3 \* 5 = 15, 15标为合数; 3 \* 6 = 18, 18标为合数;  
> 将素数5及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 将素数7及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 将素数11及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 将素数13及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 将素数17及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> 将素数19及大于其的自然数相乘寻找合数，并且合数小于指定范围内：  
> PrimeCount inside of 20: 8  
> 遍历次数: 13

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70]: /images/20221005/c8da57f829bc479cb6cbe1c1666b188f.png