C语言程序设计教程（第三版）课后习题6.7 （C语言代码）（用数组存放质数）

解题思路:一个数的质数，我看成是成对出现的，比如28的质数分为1 28 2 14 4 7，我们知道了一个小的质数后自然也就知道了另一个，我们将其存放在数组中，再排序输出就行了，所以对整数进行暴力破解时，便可以缩小了时间复杂度。

参考代码:

#include<stdio.h>

#include<math.h>

void sort(int a[],int n)

{

int t,i,j;

for(i=0;i<n-1;i++)

{

for(j=0;j<n-1-i;j++)

{

if(a[j]>a[j+1])

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

}

}

int main()

{

int n,k,b,c,f,j,i,sum; 

scanf("%d",&n);

for(i=6;i<=n;i++)//n是范围； 

{

b=sqrt(i);

sum=1;

int a[100]={0};

k=0; 

for(j=2;j<=b;j++)//暴力求质数； 

{

if(i%j==0)//对范围内的数求质数并存放于数组a中； 

{

a[k]=j;

c=i/j;

a[k+1]=c;

sum+=j+c;

k+=2;

}

}

if(i==sum)//完数输出 

{

sort(a,k);//对数组a排序； 

printf("%d its factors are 1 ",i);

for(f=0;f<k;f++)

{

if(f==k-1){

printf("%d\n",a[f]);

break;} 

printf("%d ",a[f]);

}

}//完数输出；

  }

}