4120525_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

bool isprime(int num)
{
	if (num % 2 == 0)
	{
		return false;
	}
	for (int i = 3; i * i <= num; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}
	return true;
}

int prime[210];
int cnt;
int ex_num[250];
int num;

void init()
{
	int i, j;

	cnt = 0;
	prime[cnt++] = 2;
	for (i = 3; i < 1260; i += 2)
	{
		if (isprime(i))
		{
			prime[cnt++] = i;
		}
	}
	num = 0;
	__int64 A, B, C, D;
	__int64 c1, c2, c3;
	for (i = 0; i < cnt; i++)
	{
		c1 = prime[i];
		for (j = i + 1; j < cnt; j++)
		{
			c2 = prime[j];
			if ((c2 - c1) % (c1 - 1) != 0 || (c1 * c1 - c2) % (c1 - 1) != 0)
			{
				continue;
			}
			A = (c2 - c1) / (c1 - 1);
			B = (c1 * c1 - c2) / (c1 - 1);
			c3 = c2 * A + B;
			C = c1 * c2 * c3;
			while (C <= 2000000000 && isprime((int)c3))
			{
				ex_num[num++] = C;
				c3 = c3 * A + B;
				C *= c3;
			}
		}
	}
}

int main()
{
	int t, a, b;

	init();
	scanf("%d", &t);
	while (t--)
	{
		int ans = 0;
		scanf("%d%d", &a, &b);
		for (int i = 0; i < num; i++)
		{
			ans += (ex_num[i] >= a && ex_num[i] <= b);
		}
		printf("%d\n", ans);
	}
	return 0;
}