|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 |
#include<stdio.h>#include"math.h"int howmany (int
x,int y){ int
p=x,q=y; int
a[100000]; int
c[100000]; int
t=0,i,j,m,n,chej,g=0; int
k=0,s=0,b=0,h=0; for(i=2;i<=q;i++) { //找出所有质数，存入到一个数组中 for(j=2;j<= (int)sqrt(i);j++) { if(i%j==0) {break;} } if(j > (int)sqrt(i)) { a[k++]=i; printf("质数的值:%d\n",i);//打印出质数的值 } } printf("打印出质数的个数:%d\n",k);//打印出质数的个数 //从a[]数组中任意选择两个数相乘，如果他们的乘积在x与y的范围之间 就可判断这个数是半质数 for(m=0;m<k;m++) { for(n=0;n<k;n++) { chej=a[m]*a[n]; if(p<=chej&&q>=chej) { printf("半质数为：%d\n",chej);//数字有重叠的部分，还需要去重 c[s++]=chej; } } } t=s; //取出c数组中重复的项 for(g=0;g<s;g++) { for(h=g+1;h<s;h++) { if(c[h]==c[g]) { t--; } } } printf("半质数的个数为：%d\n",s); printf("去重后半质数的个数为：%d\n",t); return
t;}//start 提示：自动阅卷起始唯一标识，请勿删除或增加。int
main(){ printf("%d",howmany(1,80000));}//end //提示：自动阅卷结束唯一标识，请勿删除或增加。 |
质数是大家熟知的概念，我们定义一个半质数的概念：如果一个数恰好是两个质数的乘积（可以相同），则称它为半质数。前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。我们的问题是，输入两个正整数x<=y，问[x,y]之间有多少个半质数？
输入:x,y
输出:[x,y]之间有多少个半质数。
输入数据范围 1<=x<=y<=2000000。
注意：1：声明int g=h=0;时编译环境报错，2：for(int i=0;i<m:i++)时报错
挑战失败 howmany函数超过80000就运行超时
原文：http://www.cnblogs.com/cc-jony/p/3573356.html