H、Diff-prime Pairs

pypy3 解法, 执行用时: 1562ms, 内存消耗: 137476K, 提交时间: 2022-04-20 19:24:54

import bisect
n = int(input())
is_prime = [1] * (n+1)
prime = []
ans = 0

for i in range(2, n+1):
    if is_prime[i]:
        prime.append(i)
        for j in range(i*i, n+1, i):
            is_prime[j] = 0

for i in range(1, n+1):
    j = bisect.bisect_right(prime, n/i)
    if j <= 1:
        break
    ans += j * (j-1)
print(ans)

C++14(g++5.4) 解法, 执行用时: 300ms, 内存消耗: 78680K, 提交时间: 2020-10-08 15:55:20

#include <bits/stdc++.h>
using namespace std;
long i=2,j,n,c,s,a[10000001];
main() 
{
    cin>>n;
    for(;i<=n;i++)
        if(!a[i]) 
		{
            s+=c*(n/i);c++;
            for(j=i*i;j<=n;j+=i)a[j]=1;
        }
    cout<<s*2;
}

C++11(clang++ 3.9) 解法, 执行用时: 267ms, 内存消耗: 78676K, 提交时间: 2020-10-08 20:51:22

#include<bits/stdc++.h>
using namespace std;
long i=2,j,n,c,s,a[10000001];
int main()
{
	cin>>n;
	for(;i<=n;i++)
	if(!a[i])
	{
		s+=c*(n/i);
		c++;
		for(j=i*i;j<=n;j+=i)
		a[j]=1;
	}
	cout<<s*2;
 }

详情