当前位置：首页 > news >正文

C语言之素数进化论

news 来源：原创 2024/5/8 16:27:44

最近，有人给我私信问我怎么用C语言求素数！！！

于是乎我这个码龄1年的小萌新就来解决他的问题。

素数，也称质数，是指只能被1和自身整除的正整数。在大于1的自然数中，2是最小的素数，其他的素数依次为3、5、7、11、13、17、19、23……。素数的特点是除了1和自身之外没有其他因数。因此，素数无法被其他数整除，也不能被分解为其他的乘积。素数在数论和密码学等领域有重要的应用。

先举个栗子100——200之间的素数。

说到素数大家一定会先这么写：

#define CRT SECURE NO WARNINGS
#include<stdio.h>
int main()
{
   int i = 0;
   int count = 0;
   for(i = 100;i <= 200;i++)
   {
       int flat = 1;
       int j = 0;
       for(j = 2;j < i;j++)
       {
           if(i % j == 0)
           {
               flat = 0;
               break;
           }
       }
       if(flat == 1)
       {
           count++;
           printf("%d ",i);

       }
   }

   printf("\ncount=%d\n",count);
   return 0;
}
#define CRT SECURE NO WARNINGS
#include<stdio.h>
int main()
{int i = 0;int count = 0;for(i = 100;i <= 200;i++){int flat = 1;int j = 0;for(j = 2;j < i;j++){if(i % j == 0){flat = 0;break;}}if(flat == 1){count++;printf("%d ",i);}}printf("\ncount=%d\n",count);return 0;
}

但这个复杂度有点高！

如果了解素数，就知道不是素数的数一定可以被小于它开方后的整数整除，所以————嘿嘿！

#define CRT SECURE NO WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{
   double i = 0;
   int count = 0;
   for(i = 100;i <= 200;i++)
   {
       int flat = 1;
       int j = 0;
       for(j = 2;j <= sqrt(i);j++)
       {
           if(int(i) % j == 0)
           {
               flat = 0;
               break;
           }
       }
       if(flat == 1)
       {
           count++;
           printf("%d ",int(i));

       }
   }

   printf("\ncount=%d\n",count);
   return 0;
}
#define CRT SECURE NO WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{double i = 0;int count = 0;for(i = 100;i <= 200;i++){int flat = 1;int j = 0;for(j = 2;j <= sqrt(i);j++){if(int(i) % j == 0){flat = 0;break;}}if(flat == 1){count++;printf("%d ",int(i));}}printf("\ncount=%d\n",count);return 0;
}

不，这还是不让计算机偷懒！！！

对了，差点忘了，好像偶数里只有2是素数！！！所以————吼吼！

#define CRT SECURE NO WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{
double i = 0;
int count = 0;
for(i = 101;i <= 200;i+=2)
{
   int flat = 1;
   int j = 0;
   for(j = 2;j <= sqrt(i);j++)
   {
       if(int(i) % j == 0)
       {
           flat = 0;
           break;
       }
   }
   if(flat == 1)
   {
       count++;
       printf("%d ",int(i));

   }
}

printf("\ncount=%d\n",count);
return 0;
}
#define CRT SECURE NO WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{
double i = 0;
int count = 0;
for(i = 101;i <= 200;i+=2)
{int flat = 1;int j = 0;for(j = 2;j <= sqrt(i);j++){if(int(i) % j == 0){flat = 0;break;}}if(flat == 1){count++;printf("%d ",int(i));}
}printf("\ncount=%d\n",count);
return 0;
}

这样就好了嘛，不不不，我还要把他变成函数。

#define CRT SECURE NO WARNINGS
#include<stdio.h>
#include<math.h>

int is_prime(double(n))
{
   int j = 0;
   for(j = 2;j <= sqrt(n);j++)
   {
       if(int(n) % j == 0)
       {
           return 0;
       }
   }
   return 1;
}

int main()
{
   double i = 0;
   int count = 0;
   for(i = 101;i <= 200;i+=2)
   {
       if(is_prime(i) == 1)
       {
           count++;
           printf("%d ",int(i));
       }
   }

   printf("\ncount=%d\n",count);
   return 0;
}
#define CRT SECURE NO WARNINGS
#include<stdio.h>
#include<math.h>int is_prime(double(n))
{int j = 0;for(j = 2;j <= sqrt(n);j++){if(int(n) % j == 0){return 0;}}return 1;
}int main()
{double i = 0;int count = 0;for(i = 101;i <= 200;i+=2){if(is_prime(i) == 1){count++;printf("%d ",int(i));}}printf("\ncount=%d\n",count);return 0;
}