求两个质数的乘积等于7140229933

来自朋友圈的数字题，使用golang实现，直接上代码了

运行

go run main.go
或
go build & ./pr

计算方法一

package main

import (
    "fmt"
    "math"
    "time"
)

var s = 7140229933

func main() {

    now := time.Now()

    //100000000以内的所有质数
    pr := GetPrimeLimit(100000000)
    for _, item := range pr {
        n := s / item
        //加上能整除的条件
        if s%item == 0 && n == IsContainsInt(pr, n) {
            fmt.Println(fmt.Sprintf("结果为：%d*%d=%d", item, n, s))
            break
        }
        fmt.Println(fmt.Sprintf("计算：%d/%d=%d", s, item, n))
    }

    fmt.Println(fmt.Sprintf("运行耗时: %v 秒", time.Now().Sub(now).Seconds()))
}

//IsContainsInt 检测si内是否包括n
func IsContainsInt(si []int, n int) int {
    for _, item := range si {
        if item == n {
            return item
        }
    }
    return 0
}

//GetPrimeLimit 求num内的所有质数
func GetPrimeLimit(num int) []int {
    primeFlag := make([]bool, num, num)
    primeFlag[2] = true
    for i := 3; i < num; i += 2 {
        primeFlag[i] = true
    }
    for i := 3; i <= int(math.Sqrt(float64(num))); i++ {
        if primeFlag[i] {
            for j := i + i; j < num; j += i {
                primeFlag[j] = false
            }
        }
    }
    prime := []int{}
    for i := 0; i < num; i++ {
        if primeFlag[i] {
            prime = append(prime, i)
        }
    }
    return prime
}

输出结果

...
计算：7140229933/83299=85718
计算：7140229933/83311=85705
计算：7140229933/83339=85676
计算：7140229933/83341=85674
计算：7140229933/83357=85658
计算：7140229933/83383=85631
计算：7140229933/83389=85625
计算：7140229933/83399=85615
计算：7140229933/83401=85613
计算：7140229933/83407=85607
计算：7140229933/83417=85596
计算：7140229933/83423=85590
计算：7140229933/83431=85582
计算：7140229933/83437=85576
计算：7140229933/83443=85570
计算：7140229933/83449=85563
计算：7140229933/83459=85553
计算：7140229933/83471=85541
计算：7140229933/83477=85535
计算：7140229933/83497=85514
计算：7140229933/83537=85473
计算：7140229933/83557=85453
计算：7140229933/83561=85449
计算：7140229933/83563=85447
计算：7140229933/83579=85430
计算：7140229933/83591=85418
计算：7140229933/83597=85412
计算：7140229933/83609=85400
计算：7140229933/83617=85392
计算：7140229933/83621=85387
计算：7140229933/83639=85369
计算：7140229933/83641=85367
计算：7140229933/83653=85355
计算：7140229933/83663=85345
计算：7140229933/83689=85318
计算：7140229933/83701=85306
计算：7140229933/83717=85290
计算：7140229933/83719=85288
计算：7140229933/83737=85269
计算：7140229933/83761=85245
计算：7140229933/83773=85233
结果为：83777*85229=7140229933
运行耗时: 1.17519967 秒

计算方法二

包括了计算方法一的代码

package main

import (
    "fmt"
    "math"
    "time"
)

var s = 7140229933

func main() {
    //MethodOne()  //方法一
    MethodTwo() //方法二
}

//=================计算方法二====================

//MethodTwo 计算方法二
func MethodTwo() {
    now := time.Now()
    item := 0
    for i := 2; i < int(math.Sqrt(float64(s))); i++ {
        if s%i == 0 {
            if isPrime(i) && isPrime(s/i) {
                item = i
                fmt.Println(fmt.Sprintf("%d=%d*%d", s, s/i, item))
            }
        }
    }
    fmt.Println(fmt.Sprintf("运行耗时: %v 秒", time.Now().Sub(now).Seconds()))
}

//isPrime 判断num是否是质数
func isPrime(num int) bool {
    if num <= 3 {
        return num > 1
    }
    if num%6 != 1 && num%6 != 5 {
        return false
    }
    sqrt := int(math.Sqrt(float64(num)))
    for i := 5; i <= sqrt; i += 6 {
        if num%i == 0 || num%(i+2) == 0 {
            return false
        }
    }

    return true
}

//=================计算方法一====================

//MethodOne 计算方法一
func MethodOne() {
    now := time.Now()

    //100000000以内的所有质数
    pr := GetPrimeLimit(100000000)
    for _, item := range pr {
        n := s / item
        //加上能整除的条件
        if s%item == 0 && n == IsContainsInt(pr, n) {
            fmt.Println(fmt.Sprintf("结果为：%d*%d=%d", item, n, s))
            break
        }
        fmt.Println(fmt.Sprintf("计算：%d/%d=%d", s, item, n))
    }

    fmt.Println(fmt.Sprintf("运行耗时: %v 秒", time.Now().Sub(now).Seconds()))
}

//IsContainsInt 检测si内是否包括n
func IsContainsInt(si []int, n int) int {
    for _, item := range si {
        if item == n {
            return item
        }
    }
    return 0
}

//GetPrimeLimit 求num内的所有质数
func GetPrimeLimit(num int) []int {
    primeFlag := make([]bool, num, num)
    primeFlag[2] = true
    for i := 3; i < num; i += 2 {
        primeFlag[i] = true
    }
    for i := 3; i <= int(math.Sqrt(float64(num))); i++ {
        if primeFlag[i] {
            for j := i + i; j < num; j += i {
                primeFlag[j] = false
            }
        }
    }
    prime := []int{}
    for i := 0; i < num; i++ {
        if primeFlag[i] {
            prime = append(prime, i)
        }
    }
    return prime
}

输出结果

7140229933=85229*83777
运行耗时: 0.000929797 秒