Concurrent Prime Finder with Go: Goroutines and Channels

Exercise: Concurrent Prime Number Finder

In this exercise, you will create a Go program that finds prime numbers concurrently. The program will use multiple goroutines to check for prime numbers in a given range and will report the primes found.

Requirements

1. Concurrency: Use goroutines to split the work of checking numbers in the given range.
2. Channels: Use channels to collect results from the goroutines.
3. Synchronization: Ensure the main goroutine waits for all worker goroutines to finish before exiting.
4. Prime Checking: Implement an efficient prime checking function.

Steps

1. Set Up Goroutines: Create a function that starts multiple worker goroutines.
2. Use Channels: Use a channel to send results from the worker goroutines to the main goroutine.
3. WaitGroup: Use a sync.WaitGroup to wait for all worker goroutines to finish.
4. Prime Checking Function: Write an efficient function to check if a number is prime.
5. Combine Results: Collect and print the prime numbers found by the worker goroutines.

Here’s a possible structure for your program:

package main

import (
	"fmt"
	"math"
	"sync"
)

// isPrime checks if a number is a prime
func isPrime(n int) bool {
	if n <= 1 {
		return false
	}
	if n == 2 {
		return true
	}
	if n%2 == 0 {
		return false
	}
	sqrt := int(math.Sqrt(float64(n)))
	for i := 3; i <= sqrt; i += 2 {
		if n%i == 0 {
			return false
		}
	}
	return true
}

// worker function to check a range of numbers for primes
func worker(start, end int, wg *sync.WaitGroup, primes chan<- int) {
	defer wg.Done()
	for num := start; num <= end; num++ {
		if isPrime(num) {
			primes <- num
		}
	}
}

func main() {
	var start, end, numWorkers int
	fmt.Printf("Enter start of the range: ")
	fmt.Scan(&start)
	fmt.Printf("Enter end of the range: ")
	fmt.Scan(&end)
	fmt.Printf("Enter number of workers: ")
	fmt.Scan(&numWorkers)

	primes := make(chan int, (end-start)/2) // Buffer size can be optimized.
	var wg sync.WaitGroup

	step := (end - start + 1) / numWorkers
	for i := 0; i < numWorkers; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			workerStart := start + i*step
			workerEnd := workerStart + step - 1
			if i == numWorkers-1 {
				workerEnd = end
			}
			worker(workerStart, workerEnd, &wg, primes)
		}(i)
	}

	go func() {
		wg.Wait()
		close(primes)
	}()

	fmt.Println("Prime numbers in the range:")
	for prime := range primes {
		fmt.Println(prime)
	}
}

What to Do:

1. Ensure the code compiles and runs correctly.
2. Experiment with different ranges and worker counts to see the effects.
3. Think about potential improvements like more optimized buffer sizes or enhanced prime-checking