BOJ基本数学(小数)

少数の人を理解してください.

少数とは何ですか。

1課は自分の数だけに分ける
これは私が何度も聞いた定義です.
小数とは反対の概念は合成数であり、1は小数と合成数ではない.
少数は2,3,5...背中がある.

どのように小数を判別しますか?

小数は1を除いて小数ではありません.
したがって、どの数Nが小数であるかを判別するために、
Nより小さい数でNで割るといいです.

約数は対称性を有する.
例えば、64の約数を見てみましょう.

64の平方根に準じて対称性を有する.

では
nより小さい平方根の数で弱い数があるかどうかを探します.

その他の注意事項

1は

を含まない

偶数を除く

2は偶数または小数であり、

を考慮すると

def is_prime(n):
    if n==2:
        return True
    if n==1 or n%2==0:
        return False
    else:
        for i in range(3, int(n**(1/2))+1):
            if n%i==0:
                return False
        return True

エラトステネスのふるい

少数が弱い数の数は少数ではない
ここでは「約数が対称性を持つ」という原理も利用した.
1~Nの水中から小数を得る.

N平方根未満の数で少数を探した.

少数の排水を除去する.

は少数しか残っていません…!

上記の原理を把握して符号化しましたがタイムアウトしました.^^

def is_prime(n):
    if n==2:
        return True
    if n==1 or n%2==0:
        return False
    else:
        for i in range(3, int(n**(1/2))+1):
            if n%i==0:
                flag = True
                return False
        return True
        
m = int(input())
n = int(input())
prime_lst = []
for i in range(2,int((n)**(1/2))+1):
    if is_prime(i) is True:
        prime_lst.append(i)

all_lst = list(range(m, n+1))
for p in prime_lst:
    l = 1
    while p*l <= n:
        l += 1
        if p*l in all_lst:
            all_lst.remove(p*l)
if 1 in all_lst:
    all_lst.remove(1)
if len(all_lst)==0:
    print(-1)
else:
    print(sum(all_lst))
    print(min(all_lst))

導入されたソリューション

def prime_list(n):
    sieve = [True]*n
    m = int(n**0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i]==True]
print(prime_list(int(input())))

コード長からかなりの差があるので賢太に打たれ、
これは

n以下の少数->各少数の倍数を探す過程ではない.

は、まず複数の数と仮定し、その後、各数の倍数を前から除去する.

キムバッハの推測

私のソリューション
私が解くとき、少数とnの組み合わせを探しているときは、半分に分けて探すのではなく、前から探して、既存の少数の組み合わせより少ない車の最小の更新方法で書いています.

def prime_list(n):
    sieve = [True]*n
    m = int(n**0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i]==True]

def gold(n):
    prime_lst = prime_list(n)
    comb1 = 0; comb2 = 100000
    for i in prime_lst:
        if (n-i) in prime_lst:
            if i == n-i:
                return i, i
            if  abs(2*i-n) < abs(comb2 - comb1):
                comb1=i; comb2=n-i
    return comb1, comb2

iteration = int(input())
for _ in range(iteration):
    n = int(input())
    comb1 , comb2 =  gold(n)
    print(comb1 , comb2)

でもタイムアウト...!

ソウルソリューション

def prime_list(n):
    sieve = [True]*n
    m = int(n**0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i]==True]
def sosu(n):
    li=prime_list(n)
    idx = max([i for i in range(len(li)) if li[i]<=n/2])
    for i in range(idx,-1,-1):
        for j in range(i,len(li)):
            if li[i]+li[j]==n:
                return [li[i], li[j]]
for _ in range(int(input())):
    n = int(input())
    print(" ".join(map(str,sosu(n))))

上記の解決策の原理は以下の通りである.

prime list(以下liと略す)は半分に分かれ、中間から前ループ(i)

に進む.

i~nまで条件を満たす数を探す(j)

コードソース