论坛 › C\C++交流 › 求一个区间的素数

4399king 发表于 2020-9-28 12:09:32

求一个区间的素数

想了很多次，没思路，卡在如何输出-1的那种情况，尤其是一个区间内既有素数也有非素数

巴巴鲁 发表于 2020-9-28 12:27:14

可以用一个变量，如flag = 0;
如果在这个区间有素数，则赋值为1
最后遍历完，判断flag的值。为0，没有素数，输出-1；反之，有素数，输出这些素数

baige 发表于 2020-9-28 12:29:37

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

//判断一个数是否是素数，是的话返回1，否则返回0
int isPrime(int num)
{
        if (num == 2)return 1;
        else if (num <= 1 || num % 2 == 0)return 0;
        for (int i = 3; i <= sqrt(num); i += 2) {
                if (num % i == 0)return 0;
        }
        return 1;
}

int main(void) {
        int a, b;
        scanf("%d %d",&a,&b);// 输入区间端值

        int cnt = 0;//计算素数个数
        for (int i = a; i <= b; i++) {
                if (isPrime(i)) {
                        cnt++;
                        if (cnt == 1)printf("%d", i);
                        else printf(" %d", i);
                }
        }
        // 如果cnt=0说明该区间没有素数
        if (cnt == 0) {
                printf("-1");
        }
        return 0;
}

jackz007 发表于 2020-9-28 13:57:34

本帖最后由 jackz007 于 2020-9-28 14:31 编辑

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

isPrime(int x)
{
      int r = 0 , k                              ;
      if(x > 1) {
                for(r ++ , k = 2 ; k < sqrt(x) + 1 ; k ++) {
                        if(k < x && ! (x % k)) {
                              r --               ;
                              break            ;
                        }
                }
      }
      return r                                 ;
}

main(void)
{
      int a , b , c , k                        ;
      scanf("%d %d" , & a , & b)               ;
      if(b < a) {
                c = a                              ;
                a = b                              ;
                b = c                              ;
      }
      for(c = 0 , k = a ; k <= b ; k ++) {
                if(isPrime(k)) {
                        if (c) printf("        ");
                        printf("%3d" , k)          ;
                        c ++                     ;
                }
      }
      if (! c) printf("-1")                      ;
}

风过无痕1989 发表于 2020-9-28 13:58:22

本帖最后由 风过无痕1989 于 2020-9-28 15:25 编辑

// 给定一个区间，求该区间内所有的素数，a<b<=10^8，且|a-b|<=1000

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

void main()
{       
      int a;         // 输入区间的最小值
      int b;         // 输入区间的最大值
      int i,k = 0,n;

L1: printf("请输入区间的左值：");
      scanf("%d",&a);
      if(a <= 1)
      {
              printf("请输入大于1数\n");
              goto L1;
       }
L2:printf("\n请输入区间右值:");
       scanf("%d",&b);
       if(b <= 1)
      {
              printf("请输入大于1的数\n");
              goto L2;
      }       
       if(a >= b || abs(a-b) > 1000 || b>100000000)
      {
          printf("区间输入错误请重新输入一个符合题设要求的数");
              goto L2;
      }

      for(n = a;n <= b;n++)
      {
          if(n > 1)
          {
                for(i = 2;i < n;i++)
                {
                      if(n % i == 0)
                      break;
                  }         
                  if(i == n)   
               {
                      printf("%d",n);
                      k++;
                 }
          }

      }
      printf("\n");
      printf("区间内共有%d个素数\n",k);
      printf("\n");
}

4399king 发表于 2020-9-28 21:51:46

第二个for循环的if后面的没看懂，能解释一下吗谢谢

4399king 发表于 2020-9-30 08:30:42

baige 发表于 2020-9-28 12:29


第二个for循环的if后面的没看懂，能解释一下吗谢谢

baige 发表于 2020-9-30 12:40:11

4399king 发表于 2020-9-30 08:30
第二个for循环的if后面的没看懂，能解释一下吗谢谢

哪个if，你发一下语句

baige 发表于 2020-9-30 12:51:59

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

//判断一个数是否是素数，是的话返回1，否则返回0
int isPrime(int num)
{
      // 偶数只有2是素数，所以num = 2返回1
      if (num == 2)return 1;
      // num <= 1 或 num是偶数 返回0
      else if (num <= 1 || num % 2 == 0)return 0;
      // num 从 3 到 根号 num
      for (int i = 3; i <= sqrt(num); i += 2) {
                // 如果 num 被 i 整除 说明 num 不是素数
                if (num % i == 0)return 0;
      }
      // 上面的循环执行完num % i ！= 0 说明num是素数，返回1
      return 1;
}

int main(void) {
      int a, b;
      scanf("%d %d",&a,&b);// 输入区间端值

      int cnt = 0;//计算素数个数
      // 遍历区间
      for (int i = a; i <= b; i++) {
                // if语句如果是素数的话成立
                if (isPrime(i)) {
                        // cnt 用来计算素数的个数
                        cnt++;
                        // cnt = 1是第一个素数 直接输出
                        if (cnt == 1)printf("%d", i);
                        // cnt != 1 输出空格+素数
                        else printf(" %d", i);
                }
      }
      // 如果cnt=0说明该区间没有素数
      if (cnt == 0) {
                printf("-1");
      }
      return 0;
}

查看完整版本: 求一个区间的素数