FC_YSN 发表于 2020-11-22 17:17:02

求助，很急！！

求助，很急！！

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

#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 发表于 2020-11-22 17:33:13

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


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

jackz007 发表于 2020-11-22 18:19:53

    这个呢？#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 发表于 2020-11-22 18:23:35

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

还是

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

#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 20:01:49

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


还是错了一部分

TOP_LK 发表于 2020-11-22 20:12:23

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')

永恒的蓝色梦想 发表于 2020-11-22 20:31:12

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

发个错误的例子呗

风过无痕1989 发表于 2020-11-23 14:39:56

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 发表于 2020-11-23 14:40:55

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

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

jackz007 发表于 2020-11-23 14:55:36

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

      顺便再测测这个：
#include <stdio.h>

int prime(int n)
{
      int c , d = {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 ++) {
                                        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")         ;
}

麻瓜瓜呀 发表于 2020-11-23 18:22:30

#include <bits/stdc++.h>

using namespace std;

bool flag;
vector<long long> ans;

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

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 发表于 2020-11-27 00:08:20

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

感谢！！
页: [1]
查看完整版本: 求助，很急！！