Pagini recente » Cod sursa (job #1136835) | Cod sursa (job #1265794) | Cod sursa (job #1334061) | Cod sursa (job #2358252) | Cod sursa (job #1938565)
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
try {
//READING PART
BufferedReader br = new BufferedReader(new FileReader("fractii.in"));
int n = Integer.valueOf(br.readLine());
br.close();
int res = 1, i,j;
boolean[] notPrime = new boolean[n+1];
List<Integer> primes = new ArrayList<Integer>();
double sqrt = Math.sqrt(n);
for (i = 2; i < sqrt; i++ ) {
j = i * 2;
while ( j <= n ) {
notPrime[j] = true;
j += i;
}
}
for ( i = 2; i <=n ; i++) {
if (!notPrime[i]) {
primes.add(i);
}
}
for (i = 2; i <= n; i++) {
double sqrt_f = Math.sqrt(i);
int t = i;
int euler = 1, prime;
j = 0;
int k = 0;
if (!notPrime[i]) {
euler = i - 1;
} else {
while (t >= 1 && j < primes.size() && primes.get(j) <= t) {
prime = primes.get(j);
//System.out.print(prime);
if (t % prime == 0) {
k++;
t /= prime;
} else {
k = 0;
j++;
}
if (k != 0) {
euler *= k == 1 ? (prime - 1) : prime;
}
}
}
res = res + 2 * euler;
//System.out.println(i +" -> " + "factors: " + euler + " res: "+ res );
}
BufferedWriter bw = new BufferedWriter(new FileWriter("fractii.out"));
bw.write(String.valueOf(res));
bw.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}