How to resolve the algorithm Unprimeable numbers step by step in the Go programming language
How to resolve the algorithm Unprimeable numbers step by step in the Go programming language
Table of Contents
Problem Statement
As used here, all unprimeable numbers (positive integers) are always expressed in base ten.
───── Definition from OEIS ─────: Unprimeable numbers are composite numbers that always remain composite when a single decimal digit of the number is changed.
───── Definition from Wiktionary (referenced from Adam Spencer's book) ─────: (arithmetic) that cannot be turned into a prime number by changing just one of its digits to any other digit. (sic)
Unprimeable numbers are also spelled: unprimable. All one─ and two─digit numbers can be turned into primes by changing a single decimal digit.
190 isn't unprimeable, because by changing the zero digit into a three yields 193, which is a prime.
The number 200 is unprimeable, since none of the numbers 201, 202, 203, ··· 209 are prime, and all the other numbers obtained by changing a single digit to produce 100, 300, 400, ··· 900, or 210, 220, 230, ··· 290 which are all even.
It is valid to change 189 into 089 by changing the 1 (one) into a 0 (zero), which then the leading zero can be removed, and then treated as if the "new" number is 89.
Show all output here, on this page.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Unprimeable numbers step by step in the Go programming language
The provided Go code finds and prints the first 35 unprimeable numbers and the 600th unprimeable number, as well as the first unprimeable number ending with each digit from 0 to 9. A number is considered unprimeable if it's composite (not prime) and cannot be transformed into a prime number by changing a single digit.
- isPrime function: Checks whether a given number is prime. It uses various optimizations to efficiently determine primality.
- commatize function: Converts a number to a comma-separated string representation for readability.
- main function:
- outer loop: Iterates through numbers starting from 100 and checks if they are unprimeable.
- if the number is prime, the loop continues to the next number.
- if the number is composite, it tries to change each digit to every other digit (except itself) and checks if the resulting number is prime. If any of the modified numbers are prime, the loop continues to the next number.
- if none of the modified numbers are prime, the number is considered unprimeable, and its count is incremented.
- firstNum array: Stores the first unprimeable number ending with each digit from 0 to 9.
- printing: The program prints the first 35 unprimeable numbers, the 600th unprimeable number with commas for readability, and the first unprimeable number ending with each digit.
Source code in the go programming language
package main
import (
"fmt"
"strconv"
)
func isPrime(n int) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
default:
d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
fmt.Println("The first 35 unprimeable numbers are:")
count := 0 // counts all unprimeable numbers
var firstNum [10]int // stores the first unprimeable number ending with each digit
outer:
for i, countFirst := 100, 0; countFirst < 10; i++ {
if isPrime(i) {
continue // unprimeable number must be composite
}
s := strconv.Itoa(i)
le := len(s)
b := []byte(s)
for j := 0; j < le; j++ {
for k := byte('0'); k <= '9'; k++ {
if s[j] == k {
continue
}
b[j] = k
n, _ := strconv.Atoi(string(b))
if isPrime(n) {
continue outer
}
}
b[j] = s[j] // restore j'th digit to what it was originally
}
lastDigit := s[le-1] - '0'
if firstNum[lastDigit] == 0 {
firstNum[lastDigit] = i
countFirst++
}
count++
if count <= 35 {
fmt.Printf("%d ", i)
}
if count == 35 {
fmt.Print("\n\nThe 600th unprimeable number is: ")
}
if count == 600 {
fmt.Printf("%s\n\n", commatize(i))
}
}
fmt.Println("The first unprimeable number that ends in:")
for i := 0; i < 10; i++ {
fmt.Printf(" %d is: %9s\n", i, commatize(firstNum[i]))
}
}
You may also check:How to resolve the algorithm Pentagram step by step in the REXX programming language
You may also check:How to resolve the algorithm Farey sequence step by step in the Yabasic programming language
You may also check:How to resolve the algorithm Pascal matrix generation step by step in the Stata programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the Yabasic programming language
You may also check:How to resolve the algorithm Haversine formula step by step in the Julia programming language