Pagini recente » Cod sursa (job #666325) | Cod sursa (job #720066) | Cod sursa (job #377003) | Cod sursa (job #3266895) | Cod sursa (job #3029988)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <deque>
#include <cmath>
using namespace std;
#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("mins.in");
ofstream fout("mins.out");
#define endl '\n'
#endif
const int NMAX = 5005;
int n, m;
int ans;
int last[NMAX];
vector<int> p;
vector<int> fact[NMAX];
void desc(int x) {
if (x == 1) return;
int n = x;
int i = 0;
while (p[i] * p[i] <= n) {
if (n % p[i] == 0) {
fact[x].push_back(p[i]);
while (n % p[i] == 0)
n /= p[i];
}
i++;
}
if (n == 1) return;
if (fact[x].empty() || fact[x].back() != n) fact[x].push_back(n);
}
void precalc() {
last[1] = 1;
p.reserve(670);
for (int i = 2; i < NMAX; i++) {
if (last[i] == 0) {
last[i] = i;
p.push_back(i);
}
for (int j = 0; j < p.size() && i * p[j] < NMAX; j++) {
last[i * p[j]] = p[j];
if (i % p[j] == 0) break;
}
}
for (int i = 1; i < NMAX; i++) {
desc(i);
}
}
bool prime(int x, int y) {
int i = 0, j = 0;
while (i < fact[x].size() && j < fact[y].size()) {
if (fact[x][i] == fact[y][j]) return false;
if (fact[x][i] < fact[y][j]) i++;
else j++;
}
return true;
}
int main() {
fin >> n >> m;
precalc();
for (int x = 1; x < n; x++) {
for (int y = 1; y < m; y++) {
ans += prime(x, y);
}
}
fout << ans;
return 0;
}