# [EASY][DOUBL] Chef and Lucky Number - All About Free

### Problem

Mr. Chef has been given a number N. He has a tendency to double whatever he get. So now he has got the number N with him and he has multiplied the number N by 2. Now Chef is superstitious. He believes in something known as Lucky Number. His lucky number is defined as any number, which when multiplied by 2 has no other factors other than 1,2, and N. If the number is lucky all you have to do is print “LUCKY NUMBER”. If the number is not a lucky number, print “Sorry”..

### Input

The first line consists of T, which is the number of test cases. Every line of the next T lines consists of N.

### Output

Print LUCKY NUMBER if the number is lucky and “Sorry” if the number is not lucky followed by a new line.

### Constraints

1<=T<=1000
1<=N<=1000000

Input
``` 3 26 12 11 ```

Output:
``` Sorry Sorry LUCKY NUMBER ```

### Solution

Golang解法

``````package main

import (
"fmt"
"math"
)

var ns []int64
var UpperboundArray []bool
var upperbound, i, j, k int64

func is_pow_of_two(n int64) bool {
return (n&(n-1) != 0)
}

func generate_prime_number_table(n int64) {
upperbound = int64(math.Sqrt(float64(n)))
UpperboundArray = make([]bool, n+1)
for i = 2; i <= upperbound; i++ {
if !UpperboundArray[i] {
for k = i * i; k <= n; k += i {
UpperboundArray[k] = true
}
}
}
}

func is_prime_number(n int64) bool {
return !UpperboundArray[n]
}

func is_lucky_number(n int64) bool {
if n < 1 || n > 1000000 {
return false
}
return is_pow_of_two(n) || is_prime_number(n)
}

func main() {
var testcases, n int64
fmt.Scanln(&testcases)
ns = make([]int64, testcases)
n = 0
for i = 0; i < testcases; i++ {
fmt.Scanln(&ns[i])
if n < ns[i] {
n = ns[i]
}
}
generate_prime_number_table(n)

for i = 0; i < testcases; i++ {
if is_lucky_number(ns[i]) {
fmt.Println("LUCKY NUMBER")
} else {
fmt.Println("Sorry")
}
}
}

``````
/
Published under (CC) BY-NC-SA in categories algorithm  codechef