#include <stdio.h> #include <math.h> int main() { int a, b; int c[1000001] = { 0,0,-1 }; memset(c + 2, -1, 999999); int sum = 0; for (int i = 2;i < 1000001;i++) { if (c[i] == -1 ) { sum++; c[i] = sum; for (int j = i * 2;j < 1000001;j += i) { c[j] = 0; } } else { c[i] = sum; } } while (scanf("%d %d", &a, &b) != EOF) { int sum = c[b]-c[a] + 1; printf("%d\n", sum); } } |
Double click to view unformatted code.