Решение задачи "Почти простые числа" с Codeforces

Без пояснения   Просмотров: 11


Число называется почти простым, если оно имеет ровно два различных простых делителя. Например, числа 6, 18, 24 являются почти простыми, а 4, 8, 9, 42 — не являются. Найдите количество почти простых чисел от 1 до n включительно.

Код

#include <bits/stdc++.h>
using namespace std;
int a[10005];
int main() {
	int n, i, j, ans = 0;
	scanf("%d", &n);
	for(i = 2; i <= n; i++) {
		if(!a[i])
			for(j = i; j <= n; j += i)
				a[j]++;
		if(a[i] == 2) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться