2012年12月16日

UVa 11408 - Count DePrimes


#include <stdio.h>
#define S 5000001

int prime[S], rec[S], fac[S], sum[S];

int main() {
  int i, j;
  prime[0] = prime[1] = 1;
  for (i = 2; i < S; i++)
    if (!prime[i]) {
      fac[i] = i;
      for (j = i + i; j < S; j += i) {
        prime[j] = 1;
        rec[j] = i;
      }
    }
  for (i = 0; i < S; i++)
    if (!fac[i] && rec[i]) {
      fac[i] = fac[i / rec[i]];
      if ((i / rec[i]) % rec[i]) fac[i] += rec[i];
    }
  for (i = 1; i < S; i++)
    sum[i] = sum[i - 1] + !prime[fac[i]];
  int a, b;
  while (scanf("%d", &a) && a) {
    scanf("%d", &b);
    printf("%d\n", sum[b] - sum[a] + !prime[fac[a]]);
  }
  return 0;
}

沒有留言:

張貼留言