问题标题: 酷町堂：3890 开心数超时了求优化方法

Question

0

已解决

陈振轩

高级光能

#include<iostream>
#include<cmath>
using namespace std;
int a, ans = 0;
bool n[1000001];
void kxs() {
    int cnt;
    for (int i = 210; i <= a; ++i) {
        if (n[i])
            continue;
        cnt = 0;
        for (int j = 2; j <= i; ++j) {
            if (!n[j]) {
                for (int k = j * 2; k <= i; k += j) {
                    n[k] = true;
                    if (k == i) {
                        ++cnt;
                    }
                }
            }
        }
        if (cnt == 4)
            ++ans;
    }
}
int main() {
    cin >> a;
    kxs();
    cout << ans;
}

#include<iostream>
#include<cmath>
using namespace std;
int a, ans = 0;
bool n[1000001];
void kxs() {
    int cnt;
    for (int i = 210; i <= a; ++i) {
        cnt = 0;
        for (int j = 2; j <= i/2; ++j) {
            if (i % j == 0 && !n[j])
                ++cnt;
            if (j != 2)
                ++j;
        }
        if (cnt == 4) {
            ans++;
        }
    }
}
int main() {
    cin >> a;
    for (int i = 2; i <= sqrt(a); ++i) {
        if (!n[i]) {
            for (int j = i * i; j <= a; j += i) {
                n[j] = true;
            }
        }
    }
    kxs();
    cout << ans;
}

超时了求优化方法

酷町豆刷题求解 C++ 2条评论 4 年，6 月前

Answer 1

已采纳

高子健

新手天翼

少年郎，我一看题目就知道，这是你作业吧！

我们作业也是这个

不说废话 上思路
------------------------------------（别打我，我是分割线）
定义一个数组（建议定义在主函数外面）整形或双长都可以（建议双长）


定义1个变量，一个计数器（计数器==0）PS：整形或双长都可以 
输出变量;
循环(2~n)//我定义的是i
    {
        判断数组i是否等于0
        {
            循环（2*i~n）//我定义的是j，不是j++
            数组j++
        }
     } 
    循环（2~n）//我定义的是i
        {
            判断（数组i等于4）
            计数器++；
}
        输出计数器；

打字不易望采纳

不对再@我

Answer 2

邓涵睿

中级天翼

你把for循环里的int改成long long试试，没必要那么复杂

核心

for(long long i=2;i<=n;i++)
if(b[i]==0)
for(long long j=i*2;j<=n;j+=i)
b[j]++;
for(long long i=2;i<=n;i++)
if(b[i]==4)
s++;
cout<<s;

Answer 3

侯平仄

新手天翼

埃氏筛变形：

a[j]=1

改成a[j]++

问题标题: 酷町堂：3890 开心数 超时了 求优化方法

3 个回答:

问题标题: 酷町堂：3890 开心数超时了求优化方法