Участник:Easik/APS

Материал из DISCOPAL
Перейти к: навигация, поиск

C / gcc

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define MAX_N 10000000
 
long f[MAX_N + 1];
long a[MAX_N + 1];
 
void pre_calc_functions();
 
int main() {
 
    int i;
    int T;
    long N;
 
    /* Pre-calculate a- & f-functions */
    pre_calc_functions();
 
    scanf("%d", &T);
    for (i = 0; i < T; i++) {
 
        scanf("%ld", &N);
        printf("%ld\n", a[N]);
 
    }
 
    return 0;
}
 
void pre_calc_functions() {
 
	long i, j;
 
    /* Pre-calculate f-function */
    for (i = 2; i <= MAX_N; i++) {
 
        if (f[i] == 0) {
 
            /* Set smallest prime factor of i */
            f[i] = i;
 
            /* Set smallest prime factor of all higher numbers divided by i (if factor is empty)
                Start with squared i, because below that there're no numbers with smallest prime factor of i, aside from i */
            for (j = i * i; j <= MAX_N; j += i) {
 
                if (f[j] == 0) {
 
                    f[j] = i;
 
                }
 
            }
 
        }
 
        /* Pre-calculate a-function */
        a[i] = a[i - 1] + f[i];
 
    }
 
}