結果

問題 No.2751 429-like Number
コンテスト
ユーザー ID 21712
提出日時 2025-04-20 18:04:15
言語 Go
(1.23.4)
結果
AC  
実行時間 448 ms / 4,000 ms
コード長 1,187 bytes
コンパイル時間 12,492 ms
コンパイル使用メモリ 250,948 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-20 18:04:36
合計ジャッジ時間 21,075 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	pr := gen()
	var q int
	Scan(&q)
	for ; q > 0 ; q-- {
		var a int
		Scan(&a)
		found := false
		for _, p := range pr {
			if p*p*p > a {
				break
			}
			if a%p == 0 {
				a /= p
				found = true
				break
			}
		}
		if !found {
			Println("No")
			continue
		}
		ans := "No"
		for _, p := range pr {
			if p*p > a {
				break
			}
			if a % p != 0 {
				continue
			}
			a /= p
			found = false
			for _, p2 := range pr {
				if p2*p2 > a {
					break
				}
				if a%p2 == 0 {
					found = true
					break
				}
			}
			if !found {
				ans = "Yes"
			}
			break
		}
		Println(ans)
	}
}

func init() {
	check()
}

func check() {
	pr := gen()
loop1:
	for x := int(25e8-1); x > 1; x-- {
		for _, p := range pr {
			if x % p == 0 {
				continue loop1
			}
		}
		for i := 0; i < 1000; i++ {
			for _, p := range pr {
				if x % p == 0 {
					break loop1
				}
			}
		}
		break
	}
}

func gen() []int {
	sv := make([]bool, 1e5+1)
	pr := append(make([]int, 0, 1e4), 2, 3)
	for p, i, j := 5, 2, 4; p*p<1e10 ; p,i,j=p+i,j,i {
		if sv[p] {
			continue
		}
		pr = append(pr, p)
		for x := p+p; x < len(sv); x += p {
			sv[x] = true
		}
	}
	return pr
}
0