Write Kikagaku-style algorithm theory in Go Primality test

What i did

I will try the udemy course I took more than half a year ago in Go language.

[Kikagaku style] Algorithm theory learned in Python to improve programming skills (Part 1) https://www.udemy.com/course/algorithm1/

Learning this course

――Do not start writing suddenly, but assemble the process in words. ――At first, assemble in the minimum range. --Write a code that works for the time being. ――Refactor from there to improve the quality. (This time the speed is improved)

Theme: Primality test

--Create a program that displays all the prime numbers up to the received value. ――We expect the following results.

> go build main.go
> ./main
100   <-input
1 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  <-output

First time

For the time being, I will try to make it move.

Processing order

i = number to be judged s = number to divide to determine

  1. Store the number you want to judge from 2 repeatedly in i
  2. If i ÷ s is divided between [1 <s <i] and it is not divisible, a prime number is output.
  3. If i ÷ s is divided between [1 <s <i], it is not a prime number and exits the loop.

code

I also measured the time taken for processing simply. Completed to get the expected result somehow

func main() {
	//1.Receive the number you want to determine the prime number from the input
	var n int
	fmt.Scan(&n)

	//Start measuring time
	start := time.Now()
	//Output only 1
	fmt.Print("1 ")

	for i := 2; i <= n; i++ {
		//2.Determine if it is a prime number
		for s := 2; 0 == 0; s++ {
			//3.Output if it is a prime number
			if  i == s {
				fmt.Printf("%d ", i)
				break
			} else if i % s == 0 {
				break
			}
		}
	}
	//End of time measurement
	end := time.Now()
	fmt.Printf("\n%f seconds\n",(end.Sub(start)).Seconds())
}
Output value Time taken(Seconds)
10 0.000154
100 0.000201
1000 0.000517
10000 0.021293
100000 1.594362
1000000 130.868357

Second time (after taking the speed improvement course)

Since it is troublesome to wait for input every time and input a value, it is corrected to pass a value to judge a prime number as an argument. Corrected so that it can be calculated efficiently by extracting the value divided by the prime number that already exists.

Processing order

Upper limit of the number to be judged as a prime number = n Numbers judged to be prime numbers = i

--Receive n as an argument --Define a slice to store prime numbers. At this time, if the contents of the slice break, add 2 first to judge it as a prime number. --- Store the number of 3> i> n in i. --Initialize falg with true. --Dividing i repeatedly by the contents of the slice --If it is divisible, set flag to false and exit the loop --If not all divisible, add to the prime slice. --Output the contents of the slice

code

At the first time, the ones that were judged to be prime numbers were output one by one, but a slice was created to store the prime numbers. In addition, it became easier to understand by storing the result of primality test in flag.

func main() {
	//Receive as an argument(Outputs prime numbers up to 100 by default)
	var n = flag.Int("num", 100, "")
	flag.Parse()
	//Define a slice to store a prime number. At this time, if the contents of the slice break, add 2 first to judge it as a prime number.
	result := []int{2}
	//Start measuring time
	start := time.Now()
	//3 > i >Store the number n in i
	for i := 3; i <= *n; i++ {
		//Initialize falg with true
		flag := true
		//Divide i repeatedly by the contents of the slice
		for _, v := range result {
			//If it is divisible, set flag to false and exit the loop
			if  i % v == 0 {
				flag = false
				break
			}
		}
		//If not all divisible, add to the prime slice.
		if flag == true {
			result = append(result, i)
		}
	}

	//Add 1 first
	app := []int{1}
	result = append(app, result...)
	//Output the contents of the slice
	for _, v := range result {
		fmt.Printf("%d ", v)
	}

	//End of time measurement
	end := time.Now()
	fmt.Printf("\n%f seconds\n",(end.Sub(start)).Seconds())
}
Output value Time taken(Seconds)
10 0.000365
100 0.000913
1000 0.004652
10000 0.016664
100000 0.369312
1000000 15.488318

3rd time (further improvement)

The second time, I was able to improve the speed by reducing the number of calculations to calculate the prime number. If you search by How to find a prime number, it says, "You can search from the number less than the square root of the number you want to judge.", So it seems that you can do it faster.

Processing order

Upper limit of the number to be judged as a prime number = n Numbers judged to be prime numbers = i

--Receive n as an argument --Define a slice to store prime numbers. At this time, if the contents of the slice break, add 2 first to judge it as a prime number. --- Store the number of 3> i> n in i. --Initialize falg with true. --Dividing i repeatedly by the contents of the slice --If it is divisible, set flag to false and exit the loop -** If the number to be divided becomes larger than the square root of the number to be divided, leave the loop as true ** --If not all divisible, add to the prime slice. --Output the contents of the slice

func main() {
    //Receive as an argument(Outputs prime numbers up to 100 by default)
    var n = flag.Int("num", 100, "")
    flag.Parse()
    //Define a slice to store a prime number. At this time, if the contents of the slice break, add 2 first to judge it as a prime number.
    result := []int{2}
    //Start measuring time
    start := time.Now()
    //3 > i >Store the number n in i.
    for i := 3; i <= *n; i++ {
        //Initialize falg with true.
        flag := true
        //Divide i repeatedly by the contents of the slice
        for _, v := range result {
            //Exit the loop when the square of v exceeds i
            if v * v > i {                         //Add this line
                break                              //Add this line
            }                                      //Add this line
            //If it is divisible, set flag to false and exit the loop
            if  i % v == 0 {
                flag = false
                break
            }
        }
        //If not all divisible, add to the prime slice.
        if flag == true {
            result = append(result, i)
        }
    }

    //Add 1 first
    app := []int{1}
    result = append(app, result...)
    //Output the contents of the slice
    for _, v := range result {
        fmt.Printf("%d ", v)
    }

    //End of time measurement
    end := time.Now()
    fmt.Printf("\n%f seconds\n",(end.Sub(start)).Seconds())
}
Output value Time taken(Seconds)
10 0.000265
100 0.000470
1000 0.002642
10000 0.006644
100000 0.053357
1000000 0.482029

4th bonus (parallel processing)

Since it is a Go language, I tried to speed up by parallel processing after studying, but it became impossible to divide by the prime numbers I have and it became slower. I divided it into four processes, but it may be faster if I increase the number of processes.


func main() {
	//Receive as an argument(Outputs prime numbers up to 100 by default)
	var n = flag.Int("num", 100, "")
	flag.Parse()
	//Distribute the processing time as evenly as possible(However, numbers less than 100 cannot be calculated accurately.)
	quarter := *n / 100
	minnum1, maxnum1 := 3, quarter*38
	minnum2, maxnum2 := quarter*38, quarter*62
	minnum3, maxnum3 := quarter*62, quarter*82
	minnum4, maxnum4 := quarter*82, *n+1
	var result1, result2, result3, result4 []int
	ch1, ch2, ch3, ch4 := make(chan bool), make(chan bool), make(chan bool), make(chan bool)
	//Start measuring time
	start := time.Now()

	//Primality test
	go func() {
		result1 = primeNumber(result1, minnum1, maxnum1)
		ch1 <- true
	}()
	go func() {
		result2 = primeNumber(result2, minnum2, maxnum2)
		ch2 <- true
	}()
	go func() {
		result3 = primeNumber(result3, minnum3, maxnum3)
		ch3 <- true
	}()
	go func() {
		result4 = primeNumber(result4, minnum4, maxnum4)
		ch4 <- true
	}()

	<-ch1
	<-ch2
	<-ch3
	<-ch4

	//Add 1 first
	app := []int{1, 2}
	result1 = append(app, result1...)
	//Output the contents of the slice
	for _, v := range result1 {
		fmt.Printf("%d ", v)
	}
	for _, v := range result2 {
		fmt.Printf("%d ", v)
	}
	for _, v := range result3 {
		fmt.Printf("%d ", v)
	}
	for _, v := range result4 {
		fmt.Printf("%d ", v)
	}
	//End of time measurement
	end := time.Now()
	fmt.Printf("\n%f seconds\n", (end.Sub(start)).Seconds())
}

func primeNumber(result []int, minnum int, maxnum int) []int {
	//minnum > i >Store the number of maxnum in i.
	for i := minnum; i < maxnum; i++ {
		//Initialize falg with true.
		flag := true
		//Divide i repeatedly by the contents of the slice
		for v := 2; ; v++ {
			//Exit the loop when the square of v exceeds i
			if v*v > i { //Add this line
				break //Add this line
			} //Add this line
			//If it is divisible, set flag to false and exit the loop
			if i%v == 0 {
				flag = false
				break
			}
		}
		//If not all divisible, add to the prime slice.
		if flag == true {
			result = append(result, i)
		}
	}
	return result
}

Summary

1st time: Judgment by dividing by all values Second time: Judgment by dividing by the obtained prime number Third time: Judgment by the prime number obtained below the square root 4th time: Primality test for all numbers below the square root in parallel processing

Output value First time(Seconds) Second time(Seconds) Third time(Seconds) 4th(Seconds)
10 0.000154 0.000365 0.000265 Undecidable
10^3 0.000517 0.004652 0.002642 0.002725
10^4 0.021293 0.016664 0.006644 0.007438
10^5 1.594362 0.369312 0.053357 0.055468
10^6 130.868357 15.488318 0.482029 0.502561
10^7 Unmeasurable 785.677291 4.943015 5.682649
10^8 Unmeasurable Unmeasurable 63.365127 91.279915

chart.png

This time, in the udemy speed improvement course, there was an explanation up to the second improvement, but when I investigated and improved it myself, it became faster. Since it is a Go language, I tried it with parallel processing, but the result was that the optimum algorithm could not be used, it was slow, and the efficiency was overwhelmingly poor. Also, in the third code, I managed to get closer to O (n).

Impressions

I myself am a beginner in programming who is studying acclaim, but I thought that it was a perfect introduction to algorithms. Also, the act of verbalization, which is always done in the course, was a good learning for me personally because I felt that I wanted to realize it by programming and it was an important process to connect the programs.

reference

How to calculate the processing time taken by golang? [Go] Basic Grammar ④ (Array / Slice) Parse command line arguments with Go language (golang) flag package Safely combine two slices in Go Go language type conversion int ⇔ float64 # 05 [Go] Basic Grammar ⑦ (Parallel Processing)

Recommended Posts

Write Kikagaku-style algorithm theory in Go Primality test
Algorithm in Python (primality test)
Write Pulumi in Go
To write a test in Go, first design the interface
Write A * (A-star) algorithm in Python
Write selenium test code in python
Write tests in GO language + gin
Write the test in a python docstring
Prime number enumeration and primality test in Python
Basic information Write the 2018 fall algorithm problem in Python
I want to write in Python! (2) Let's write a test