C 语言统计素数

30/03/2018 00:00

点击量：次

C语言

C语言

源码如下：

#include<stdio.h>
int main()
{
    // 1-1000的素数
    printf("1-1000的素数: \n\n"); 
    int i, j, co = 0; //设置co用于统计个数
    for (j = 1; j <= 1000; j++) //遍历1-1000
    {
        for (i = 2; i < j; i++) //素数条件：只能被1和自身整除
        {
            if (j % i == 0) //发现不是素数，则跳出本层循环
            {
                break;
            }
        }
        if (i == j) //遍历后，没有除1和自身以外的因数，i==j 表示遍历了 2--自身的所有数并且未发现因数
        {
            printf("%d ", j);
            co++;
        }
    }
    printf("\nTotal: %d\n\n", co);
}	   

运行结果：

1-1000的素数:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 
199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 
313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 
433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 
563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 
673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 
811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 
941 947 953 967 971 977 983 991 997

total: 168

注意

素数，又称质数，即整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。将1-1000中每个数都对“2–自身”进行整除，i==j 说明是对“2–自身”都遍历了一遍并且未发现符合条件的数，而不是前面发现有多余因数的break;

另一个优化的版本，供参考：

#include<stdio.h>
#include<math.h>
int main()
{
    // 1-1000的素数
    printf("1-1000的素数: \n\n"); 
    int i, j, co = 0;
    printf("2 ");
    for (j = 3; j <= 1000; j+=2) //不遍历偶数，除了2偶数都不是质数
    {
        for (i = 2; i <= sqrt(j); i++) //实际遍历到此数的平方根就够了，需要引入 <math.h> 头文件
        {
            if (j % i == 0)
            {
                break;
            }
	    }
	if (i > sqrt(j)) //这里也要变一下
	{
	    printf("%d ", j);
	    co++;
	}
    }
    printf("\n\ntotal: %d\n\n", co+1); //注意这里要加上“2”这个数，2是质数也是偶数，之前没有遍历
}

这样就大大缩短了时间。

C 语言统计素数

源码如下：

运行结果：

注意

另一个优化的版本，供参考：

评论：