编程珠玑（续） 读书笔记

前言  《ACM通讯》

一次一章，仔细地读

ANSI American National Standards Institute  美国国家标准学会

1.1计算素数

P1

#include<stdio.h>

int prime(int n )
{
int i;
for(i =2;i<n;i++){              999  //  程序段后面的数字是用性能监视工具 监视到的 运行次数 ，后面的雷同
if(n%i==0)                  78022
return 0;　　　　　　　　 831
return 1;                   168
    }
}

main()         
{    
int i ,n;
    n=1000;                         1
for(i=2;i<=n;i++)               1
    {
if(prime(i))                999
        {
            printf("%d ",i);        168
        }
    }

}

素数概念：

1.就是在所有比1大的整数中，除了1和它本身以外，不再有别的约数，这种整数叫做质数或素数。还可以说成质数只有1和它本身两个约数。

 2.素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任
  何其它两个整数的乘积。

P2 考虑n不超过∫n的可能的整数因子 程序将变得有效    调用次数也缩减

#include<stdio.h>
#include<math.h>
int root(int n )
{
return (int) sqrt((float)n);　　　　 　　5456
}

int prime(int n)
{
int i;
for(i =2;i<root(n);i++)                 999
    {
if(n%i==0)                          5288
　　　　　return 0;                 　　　　　 831        return 1;　　　　　　　　　　　　　　　  168
    }
}

main(){
int i ,n;
    n=1000;                                  1
for(i=2;i<=n;i++){                       1
if(prime(i))                             999　　
        printf("%d ",i);　　　　　　　　　　　　168
    }　　
}

 

过程试讲性能监视说明，sqrt占用的时间最多。P3将sqrt函数移到for循环之外，

#include<stdio.h>
#include<math.h>
int root(int n )
{
    return (int) sqrt((float)n);　　　　 　　5456
}

int prime(int n)
{
 int i,bound;
    bound =root(n);
    for(i =2;i<bound;i++)                 999
    {
        if(n%i==0)                          5288
　　　　　return 0;                 　　　　　 831
        return 1;　　　　　　　　　　　　　　　  168
    }
}

main(){
    int i ,n;
    n=1000;                                  1
    for(i=2;i<=n;i++){                       1
    if(prime(i))                             999　　
        printf("%d ",i);　　　　　　　　　　　　168
    }　　
}

P4

通过对 被 2 ，3 ，5 整除 的特殊检验。消除了， 1/2,1/3,1/5的数，但是有问题 ，2,3,5在这个程序中并没有输出

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

int root(int n){
return (int) sqrt((float)n);
}
int prime(int n)
{
int i,bound;
if(n%2==0)
return 0;
if(n%3==0)
return 0;
if(n%5==0)
return 0;
    bound =root(n);
for(i = 7;i<=bound;i=i+2)
    {    if(n%i==0)return 0;
return 1;
    }
}

main()
{
int i,n;
    n=1000;
for(i =2;i<=n;i++){
if(prime(i))
            printf("%d ",i);
    }
}

 

正确的检验 为

if(n%2==0)
return (n==2); 同样 3， 5 也如此,这样就避免了错误

P5 把费时的开方换成了乘法

for(i = 7;i*i<=n;i=i+2)
{
if(n%i == 0)
return 0;
return 1;        
}

当你调优单个子过程或函数的性能时，性能监视工具能告诉你运行时间都花在哪里.

1.2 使用性能监视工具
价值所在。使用监视工具，将大大缩减我们对程序修改的效率，把我们的程序变得更加的完美。

1.3专用的性能监视工具
UNIX管道pipeline

1.4开发性能监视工具

1.5原理
使用和开发 性能监视工具