Question

C++动态分班：求思路和代码，不要太深，我是新手。。谢谢

【题目描述】
某中学对班级实行动态管理，每学年结束后都要重新分配班级，但这所学校重新分配的方法和本中学完全不同。
现在给出一些属于同一年级学生的连续编号，它们都是从 A 到 B 的整数。一开始每个编号都属于各自不同的班（即一个班只有一个学生），然后学校将进行以下的调整：
每次选择两个属于不同班的编号，如果这两个编号拥有大于或等于 P 的公共质因数，那么就把她们所在的班合并成一个班。反复上述操作，直到没有可以合并的班为止。
现在请你求出最后这个年级有多少个班？

【输入】

一行，三个整数 A，B，P，其中 A≤B≤100000，2≤P≤B。

【输出】

一个数表示最终班的个数。

【输入样例】

10 20 3

【输出样例】

7

【提示】

【样例说明】
样例解释：最后只有 7 个班：{10,20,12,15,18},{11},{13},{14},{16},{17},{19}
【数据规模】
有 80%的数据 B≤1000

Answer 1

#include <iostream>
#include <cstring>
using namespace std;

const int SIZE = 100000;

int parent[SIZE + 100];
bool has_student[SIZE + 100];

int plist[SIZE + 10];
int pnum;

int find(int a) {
	if (a != parent[a]) {
		parent[a] = find(parent[a]);
	}
	return parent[a];
}

void init() {
	memset(plist, 0, sizeof(plist));
	pnum = 0;
	for (int i = 2; i < SIZE; i++) {
		if (plist[i]) continue;
		parent[pnum] = pnum;
		has_student[pnum] = false;
		plist[pnum++] = i;
		if (i >= SIZE / i) continue;
		for (int j = i * i; j < SIZE; j += i) {
			plist[j] = true;
		}
	}
}

int main() {
	int A, B, P;
	init();
	cin >> A >> B >> P;
	int counts = 0;
	for (int i = A; i <= B; i++) {
		int temp = i;
		int factors = -1;
		for (int j = 0; j < pnum && plist[j] <= temp; j++) {
			if (temp % plist[j]) continue;
			while (temp % plist[j] == 0) temp /= plist[j];
			if (factors == -1 && plist[j] >= P) {
				factors = plist[j];
				int pf = find(factors);
				has_student[pf] = true;
			}
			else {
				int pf = find(factors);
				int pp = find(plist[j]);
				if (pf != pp) {
					parent[pf] = pp;
					has_student[pp] = true;
				}
			}
		}
	}
	for (int i = 0; i < pnum; i++) {
		if (parent[i] == i && has_student[i]) {
			counts++;
		}
	}
	cout << counts << endl;
//	system("pause");
}