View Code of Problem 103

#include <stdio.h>
#include <math.h>
//1000001
//10001
int isPrime(int i) {
	if (i == 0 || i == 1) {
		return 0;
	}
	for (int j = 2;j <= sqrt(i);j++) {
		if (i%j == 0) {
			return 0;
			break;
		}
	}
	return 1;
}

int main() {
	int a, b;
	int c[1000001] = { 0 };
	int sum = 0;
	for (int i = 2;i < 1000001;i++) {
		if (c[i] == 0 ) {
			sum++;
			c[i] = sum;
			for (int j = i * 2;j < 1000001;j += i) {
				c[j] = -1;
			}
		}
		else {
			c[i] = sum;
		}
	}
	while (scanf("%d %d", &a, &b) != EOF) {
		int sum = 0;
		if (isPrime(a)) {
			sum = c[b] - c[a] + 1;
		}
		else {
			sum = c[b] - c[a];
		}
		printf("%d\n", sum);
	}
}