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())
}

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())
}

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())
}

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

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)