UVA-Code/543(Goldbag).cpp at master · misbahulhoque/UVA-Code · GitHub

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
#include<stdio.h>

long int num_flag[999983],prime_list[78499];

int main()
{
	long int i,k,m,number;
	for(i=0;i<999983;i++)
		num_flag[i]=0;
	num_flag[0]=1;
	num_flag[1]=1;

	number=2;
	k=0;
	while(number<=999983)
	{
		if(num_flag[number]!=0)
		{
			number++;
			continue;
		}
		else if(num_flag[number]==0)
		{
			prime_list[k]=number;
			k++;
			m=2*number;
			while(m<999983)
			{
				if(num_flag[m]!=1)
					num_flag[m]=1;
				m=m+number;
			}
		}
		number++;
	}

	long int p,n,x;
	long int j;

	while(1)
	{
		scanf("%ld",&n);
		if(n==0)
			break;
		for(i=0;i<k;i++)
		{
			if(prime_list[i]<=n)
				x=i;
			else
				break;
		}
		long int t=0,prime_sum;
		p=0;
		for(i=0;i<x;i++)
		{
			for(j=x;j>=0;j--)
			{
				prime_sum=prime_list[i]+prime_list[j];
				if(prime_sum==n)
				{
					t=1;
					p++;
					printf("%ld = %ld + %ld\n",n,prime_list[i],prime_list[j]);
					break;
				}
				else if(prime_sum<n)
					break;
			}
			if(t==1)
				break;
		}
		if(t==0)
			printf("Goldbach's conjecture is wrong.\n");

	}
	return 0;
}