c语言求解并输出600-900间以7结尾的素数及其个数

Answer 1

#include <stdio.h>

#include <stdlib.h>

//线性表

typedef struct Vector {

int* num;//一个数组

int length;//num数组的长度

};

//生成素数表,采用埃拉托色尼筛法

Vector* getPrimeTable(int length) {

int i, j;

int* table = (int*)malloc(sizeof(int) * length + 2);//素数表(下标表示数值,素组元素的内容表示下标是否为素数)

Vector* result = (Vector*)malloc(sizeof(Vector));//素数表(保存最终的结果)

for (i = 0; i <= length; i++)

table[i] = 1;//全部标记为素数

for (i = 2; i <= length; i++) {//整体遍历一遍数组

if (table[i] == 1) {//如果i是素数

for (j = 2; j * i <= length; j++) {//将所有i的倍数都取消素数标记

table[j * i] = 0;//撤销j的素数标记

}

}

}

result->num = (int*)malloc(sizeof(int) * length);//分配内存

result->length = 0;//赋初始值

for (i = 2; i <= length; i++) {//由于table是用数组元素的内容来表示下标对应的数是否为素数，因此需要转化为只保存素数的线性表

if (table[i] == 1) {

result->num[result->length++] = i;

}

}

return result;

}

//根据素数表找出素数,素数表的长度只有10,因此二重for循环的迭代次数大约为10*20=200次

Vector* getPrime(Vector* table, Vector* num) {

Vector* res = (Vector*)malloc(sizeof(Vector));

res->num = (int*)malloc(sizeof(int) * 10);

res->length = 0;

int i, j;

for (i = 0; i < num->length; i++) {

for (j = 0; j < table->length; j++) {

if (num->num[i] % table->num[j] == 0) {//若num中的数能够被table整除,说明该数不是素数

break;//不是素数,跳出循环

}

if (j == table->length - 1) {//如果j循环到了最后一次那么说明num中的数不能被任何table中的数字整除，因此该数一定是素数

res->num[res->length++] = num->num[i];//保存素数到结果集

}

}

}

return res;

}

int main() {

int tblLength = 30;//素数表的长度是30，因为30^2=900

Vector* tbl = getPrimeTable(tblLength);//素数表

Vector* res;//结果

Vector* input = (Vector*)malloc(sizeof(Vector));//600-900所有以7结尾的数

int i;

input->num = (int*)malloc(sizeof(int) * 10);//分配内存

input->length = 0;//设置初始值

for (i = 607; i < 900; i+=10) {

input->num[input->length++] = i;//将所有600-900以7结尾的数存入input

}

res = getPrime(tbl, input);//获取素数表

printf("一共有%d个\n",res->length);//输出结果

for (int i = 0; i < res->length; i++) {

printf("%d\n", res->num[i]);

}

}

如果你是需要算法课的程序，那么我这个程序的时间复杂度还可以。如果你需要C语言课的程序的话，我比较推荐直接穷举。

Answer 2

so easy！！

int IsPrime(int n){
int Yes=1,i;
for (i=2;2*i<=n;i++)
if (n % i == 0){
Yes = 0;
break;
}
return Yes;
}