当前位置: 首页 > >

c语言判断素数代码_go 素数筛,完美展现go并发!

发布时间:

go 被成为21世界的C语言,提到go语言,最先想到的就是支持高并发!


下面就看一段完美体现go高并发的代码示例及我对该代码的优化:


//代码来自go语言高级编程中示例代码:



1.6 常见的并发模式 ? Go语言高级编程?chai2010.cn





func GenerateNatural() chan int {
ch := make(chan int)
go func() {
for i := 2; ; i++ {
ch <- i
}
}()
return ch
}
func PrimeFilter(in <-chan int, prime int) chan int {
out := make(chan int)
go func() {
for {
if i := <-in; i%prime != 0 {
out <- i
}
}
}()
return out
}
func main() {
ch := GenerateNatural() // 自然数序列: 2, 3, 4, ...
for i := 0; i < 100; i++ {
prime := <-ch // 新出现的素数
fmt.Printf("%v: %vn", i+1, prime)
ch = PrimeFilter(ch, prime) // 基于新素数构造的过滤器
}
}


简单几个函数,将高并发体现的淋漓尽致!


分析一下该代码是筛选素数的原理:


由 GenerateNatural() 函数不断产生自然数序列,从2开始,将生成的自然数序列通过PrimeFilter() 对自然数进行过滤。注意一下 ,PrimeFilter() 函数的goruntine 内是一个for{} 的死循环,意思就是会一直运行,直到程序退出!


PrimeFilter()每次启动会初始化一个channel,作为下一个筛子的输入管道,当有新的自然数过来的时候,由最开始生成的筛子过滤,如果不能被该筛子整除,则通过该筛子初始化的时候的管道将自然数传递到下一级筛子,知道最大筛子也无法整除,则判定为素数,输出!


分析完该代码,看下该代码是否有可以优化的空间?


可以从一下几个地方入手:


1.素数肯定不是偶数,因为肯定被2整除,所以前面的自然数可以每次加2


2.是不是一定要过滤到最后一个素数不能被整除才认为该数是素数呢?答案是必须的。


假设存在素数n,如果 a*a > n,如果 n 能被正整数 x 整除,结果为y,则 x < a 或y

所以在过滤正整数 n 时候判断当前素数的*方大于 n ,切无法被整除的时候,则可以结束判定!


改进后代码如下:



package main

import (
"fmt"
"time"
)

func GenerateNatural() chan int {
ch := make(chan int)
go func() {
for i := 3; ; i += 2 {
ch <- i
}
}()
return ch
}
var Cm chan int

func PrimeFilter(in <-chan int, prime int) chan int {
out := make(chan int)
Cm = out //每次调用该函数初始化筛子的时候该筛子必为最大一个,
go func() {
for {
if i := <-in; i%prime != 0 {
if i < prime*prime { //满足临界条件,直接将值传递给最后一个素数筛
Cm <- i
} else {
out <- i
}
}
}
}()
return out
}

func OldPrimeFilter(in <-chan int, prime int) chan int {
out := make(chan int)
go func() {
for {
if i := <-in; i%prime != 0 {
out <- i
}
}
}()
return out
}

func StartOldPrime() {
ch := GenerateNatural() // 自然数序列: 2, 3, 4, ...
fmt.Println("0:2") // 2是最小的质数
for i := 1; i < 10000; i++ {
prime := <-ch
// fmt.Printf("%d:%d n", i, prime) // 新出现的素数
if i == 823 {//随机找个中间节点输出结果,检查两种方式结果是否一致
fmt.Printf("%d:%d n", i, prime)
}
ch = OldPrimeFilter(ch, prime) // 基于新素数构造的过滤器
}
}

func StartNewPrime() {
ch := GenerateNatural() // 自然数序列: 2, 3, 4, ...
fmt.Println("0:2")
for i := 1; i < 10000; i++ {
prime := <-ch
// fmt.Printf("%d:%d n", i, prime) // 新出现的素数
if i == 823 { //随机找个中间节点输出结果,检查两种方式结果是否一致
fmt.Printf("%d:%d n", i, prime)
}
ch = PrimeFilter(ch, prime) // 基于新素数构造的过滤器
}
}
func main() {
t1 := time.Now().UnixNano()
StartOldPrime()
t2 := time.Now().UnixNano()
fmt.Println(t2 - t1)
StartNewPrime()
fmt.Println(time.Now().UnixNano() - t2)
}


实际测试可以看到,在计算前10000个质数时,速度能快20倍左右,并随着计算的数据量越大速度差距越大!







相关资源:ARIMA模型-matlab代码



友情链接: