[已解决]求助，很急！！

FC_YSN

求助，很急！！

最佳答案

月排行榜 / 总排行榜

jackz007

2020-11-23 14:55:36

FC_YSN 发表于 2020-11-22 18:23
还是

        顺便再测测这个：

#include <stdio.h>

int prime(int n)
{
        int c , d[4] = {2 , 4 , 2 , 2} , f = 0 , k      ;
        if(n > 1) {
                if(n < 127) {
                        for(f = 1 , k = 2 ; k * k < n + 1  ; k += 1) {
                                if(k < n && ! (n % k)) {
                                        f = 0           ;
                                        break           ;
                                }
                        }
                } else {
                        if(n % 2 && n % 3 && n % 5 && n % 7) {
                                for(c = 0 , f = 1 , k = 11 ; k * k < n + 1 ; k += d[c % 4] , c ++) {
                                        if(k < n && ! (n % k)) {
                                                f = 0   ;
                                                break   ;
                                        }
                                }
                        }        
                }
        }
        return f                                        ;
}

int main(void)
{
        int n                        ;
        scanf("%d" , & n)            ;
        if(prime(n)) printf("Yes\n") ;
        else printf("No.\n")         ;
}

跳转到最佳答案楼层

jackz007

#include <stdio.h>

int main(void)
{
        int d , f = 0 , k             ;
        scanf("%d" , & d)             ;
        if(d > 1) {
                for(f = 1 , k = 2 ; k * k < d + 1 ; k ++) {
                        if(k < d && ! (d % k)) {
                                f = 0 ;
                                break ;
                        }
                }
        }
        if(f) printf("Yes\n")         ;
        else printf("No.\n")          ;
}

FC_YSN

jackz007 发表于 2020-11-22 17:24

他说运行超时了，能再优化点么？

jackz007

    这个呢？

#include <stdio.h>

int prime(int n)
{
        int f = 0 , k                                                  ;
        if(n > 1) {
                if(n < 11) {
                        if(n == 2 || n == 3 || n == 5 || n == 7) f = 1 ;
                } else {
                        if(n % 10 == 1 || n % 10 == 3 || n % 10 == 7 || n % 10 == 9) {
                                for(f = 1 , k = 2 ; k * k < n + 1  ; k ++) {
                                        if(k < n && ! (n % k)) {
                                                f = 0                  ;
                                                break                  ;
                                        }
                                }
                        }
                }
        }
        return f                                                       ;
}

int main(void)
{
        int n                        ;
        scanf("%d" , & n)            ;
        if(prime(n)) printf("Yes\n") ;
        else printf("No.\n")         ;
}

FC_YSN

jackz007 发表于 2020-11-22 18:19
这个呢？

还是

永恒的蓝色梦想

#include<stdio.h>
#include<math.h>



int main() {
    unsigned int i, n;
    double root;
    char temp = getchar();


    if (temp - '-') {
        temp -= '0';
        i = temp;

        for (;;) {
            switch (temp = getchar()) {
            case '\0':
            case '\n':
            case '\r':
            case EOF:
                switch (i % 6) {
                case 1:
                case 5:
                    root = sqrt(i);

                    for (n = 3; n <= root; n += 2) {
                        if (!(i % n)) {
                            goto END;
                        }
                    }

                    puts("Yes");
                    return 0;
                }

                goto END;
            }

            i *= 10;
            temp -= '0';
            i += temp;
        }
    }
    else {
    END:
        puts("No");
        return 0;
    }
}

FC_YSN

永恒的蓝色梦想 发表于 2020-11-22 18:54

还是错了一部分

TOP_LK

from math import sqrt
num = int(input())
end = int(sqrt(num))
is_prime = True
for x in range(2, end + 1):
    if num % x == 0:
        is_prime = False
        break
if is_prime and num != 1:
    print('yes')
else:
    print('no')

永恒的蓝色梦想

FC_YSN 发表于 2020-11-22 20:01
还是错了一部分

发个错误的例子呗

风过无痕1989

jackz007 发表于 2020-11-22 17:24

#include<stdio.h>
#include<math.h>
int main()
{
    int num,i;
    scanf("%d",&num);
    for (i = 2;i < sqrt(num);i++)
    {
        if(num % i == 0)
        {
            printf("No");
            break;
        }
        else if(i >= num / 2)
        {
            printf("Yes");
            break;
        }
    }
    return 0;
}

风过无痕1989

FC_YSN 发表于 2020-11-22 17:33
他说运行超时了，能再优化点么？

上面的程序，回复时点错了对象

jackz007

FC_YSN 发表于 2020-11-22 18:23
还是

        顺便再测测这个：

#include <stdio.h>

int prime(int n)
{
        int c , d[4] = {2 , 4 , 2 , 2} , f = 0 , k      ;
        if(n > 1) {
                if(n < 127) {
                        for(f = 1 , k = 2 ; k * k < n + 1  ; k += 1) {
                                if(k < n && ! (n % k)) {
                                        f = 0           ;
                                        break           ;
                                }
                        }
                } else {
                        if(n % 2 && n % 3 && n % 5 && n % 7) {
                                for(c = 0 , f = 1 , k = 11 ; k * k < n + 1 ; k += d[c % 4] , c ++) {
                                        if(k < n && ! (n % k)) {
                                                f = 0   ;
                                                break   ;
                                        }
                                }
                        }        
                }
        }
        return f                                        ;
}

int main(void)
{
        int n                        ;
        scanf("%d" , & n)            ;
        if(prime(n)) printf("Yes\n") ;
        else printf("No.\n")         ;
}

麻瓜瓜呀

#include <bits/stdc++.h>

using namespace std;

bool flag[2147483648];
vector<long long> ans;

bool prime(long long n)
{
    fill(flag, flag + n, false);
    flag[0] = flag[1] = true;
    for (long long i = 2; i <= n; i++)
    {
        if (!flag[i])
            ans.push_back(i);
        for (long long j = 0; j < ans.size() && i * ans[j] <= n; j++)
        {
            flag[i * ans[j]] = true;
            if (i % ans[j] == 0)
                break;
        }
    }
    
    return !flag[n];
}

int main(int argc, const char *argv[])
{
    long long n;
    cin >> n;
    
    if (n < 0)
    {
        cout << "No" << endl;
        return 0;
    }
    if (prime(n))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

线性筛法，时间复杂度O(n).

FC_YSN

jackz007 发表于 2020-11-23 14:55
顺便再测测这个：

感谢！！