DEV Community

Discussion on: Write a program or script to find Lucky Numbers

Collapse
 
nektro profile image
Meghan (she/her)

I also made a Go implementation that does 1,000,000 in 3s

func findLuckyNumbersTo(n int) []int {
    start := time.Now()
    lucky := make([]int, n)
    for i := 0; i < n; i++ {
        lucky[i] = i + 1
    }
    for i := 2; i < len(lucky); {
        for j := i; j <= len(lucky); j += i {
            lucky[j-1] = n + 1
        }

        k := 0
        for j := 0; j < len(lucky); j++ {
            if lucky[j] != n+1 {
                k += 1
            }
        }
        luk_tmp := make([]int, k)
        l := 0
        for j := 0; j < len(lucky); j++ {
            if lucky[j] != n+1 {
                luk_tmp[l] = lucky[j]
                l += 1
            }
        }
        lucky = luk_tmp

        for j := 0; j < len(lucky); j++ {
            if lucky[j] >= i+1 {
                i = lucky[j]
                break
            }
        }
    }
    end := time.Now()
    dur := end.Sub(start)
    fmt.Printf("size:%d,\tlength:%d,\ttime:%f\n", n, len(lucky), dur.Seconds())
    return lucky
}
Collapse
 
heikodudzus profile image
Heiko Dudzus • Edited

1.6 on my Laptop. I could speed this one up to 1.2 by counting every element you set to n+1. Then:

k := len(lucky) - counter

No need for the second inner loop (counting up k), then.

Nice. My best Go attempt on an array was 6.5s. I have to think about, why this is faster.