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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
void genp(int *);
int main()
{
int i,k=0,a,b,max,L,U,*p,sum,phi;
FILE *in,*out;
p = (int*) malloc(sizeof(int)*1000000);
in = fopen("prime.in" ,"r");
out = fopen("prime.out","w");
if(in!=NULL && out!=NULL)
{
genp(p);
fscanf(in,"%d%d",&L,&U);
while (L!=(-1))
{
k++;
max = -1000000;
for(a=L ; a<=U ; a++)
{
sum=0;
for(b=a ; b<=U ; b++)
{
sum += p[b];
phi = sum -(b-a+1);
if(phi>max) max = phi;
}
}
fprintf(out,"%d. %d",k,max);
fscanf(in,"%d%d",&L,&U);
if(L!=(-1)) fprintf(out,"\n");
}
}
return 0;
}
void genp(int *p)
{
int i,ok,a,j,k=4,premier[100000];
premier[3] = 7 ;
p[1] = 0 ; p[2] = -1; p[3] = -1; p[4] = 2; p[5] = -1; p[6] = 2; p[7] = -1;
for(i=8 ; i<=999999 ; i++)
{
ok=1;
if(i%2!=0)
{
if(i%3!=0)
{
if(i%5!=0)
{
if(i%7!=0)
{
for(j=3; premier[j]<=sqrt(i) ; j++) // verifier est ce i est premier ou non
{
a=i/premier[j];
if(i%premier[j]==0)
{
if(p[a]==(-1)) p[i] = 2;
else p[i] = p[a]+1;
ok=0;
break;
}
}
if(ok) // i est premier
{
p[i]=-1;
premier[k]=i;
k++;
}
}
else // i%7==0
{
a=i/7;
if(p[a]!=(-1)) p[i] = p[a]+1;
else p[i]=2;
}
}
else // i%5==0
{
a=i/5;
if(p[a]!=(-1)) p[i] = p[a]+1;
else p[i]=2;
}
}
else // i%3==0
{
a=i/3;
if(p[a]!=(-1)) p[i] = p[a]+1;
else p[i]=2;
}
}
else // i%2==0
{
a=i/2;
if(p[a]!=(-1)) p[i] = p[a]+1;
else p[i]=2;
}
}
} |
