我的想法是依次对每一个数字做质因数分解，在这个过程中，记录每一个质数第一次出现时，对应的数，例如输入10 20 3；第一次出现5对应10，3对应12，那么后续的比如15分解得到3、5，就检索发现质数记录表上，3对应12，就将12与15合并；5对应10，就将15与10合并。这个就是我的主要思路，超时了七个点，这个思路可以做时间上的优化吗？还是说直接换一个思路处理

# include <stdio.h>

int zhi[100005] = { 0 };

void qiuzhi(int x, int a[], int q);
void union_ (int x,int y,int a[]);

int main()
{
	int a, b, q;
	int i;
	int ans = 0;
	int x[100005] = { 0 };

	scanf("%d %d %d", &a, &b, &q);

	for (i = a; i <= b; i++) {
		x[i] = -1;
		qiuzhi(i,x,q);
	}

	for (i = a; i <= b; i++) {
		if (x[i] == -1) {
			ans++;
		}
	}

	printf("%d", ans);

	return 0;
	
}

void qiuzhi(int x,int a[],int q) 
{
	int i;
	int m;
	int y=x;
	int zh[1000] = { 0 };

	for (i = 2; i  <= y; i++) {

		if (y % i == 0) {
			if (i >= q) {
				if (zhi[i] == 0) {
					zhi[i] = x;
				}
				else {
					m = zhi[i];
					if(a[x]==-1){
						a[x] = m;
					}else{
						while(a[x]!=-1){
							x=a[x];
						}
						a[x]=m;
					}
				}
			}
		}

		while (y % i == 0) {
			y = y / i;
		}
	}
}