[C]Perfect Number

Perfect Number

定義「A positive integer is a perfect number if it is equal to the sum of all its factors except itself.」。

例如：6 = 1 + 2 + 3；28 = 1 + 2 + 4 + 7 +14。

請以「隨機」的方式將 10000以內的 Perfect Number 印出。

有兩種方式，可以透過#define V1控制執行的解答方法

SOLUTION CODE

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


//#define V1
#ifdef V1

int main (int argc, char *argv[]) {

	int choice, step, i, j, sum, count, countOfPrint;
	int perfectNumber[100];
	int *pMark;

	srand(time(NULL));

	while(true) {
		choice = 0, step = 1, count = 0, countOfPrint = 0;	//各種選擇、計數都先歸零
		printf("請選擇\n  (1)進入程式\n  (2)離開程式\n> ");
		fflush(stdin);
		scanf_s("%d", &choice);

		if(choice == 1) {
			step = 2;
			printf("\n");
		} else if(choice == 2) {
			printf("See you!!\n");
			return 0;
		} else
			printf("\n輸入錯誤 請重新輸入\n\n");

		if(step == 2) {	//先把小於10000的prefect number找出來
			for(i = 6;i <= 10000;i++) {
				
				//先計算sum of factor
				sum = 0;	//計算總和前先歸零
				for(j = 1;j < i;j++) {
					if(i%j == 0)
						sum = sum + j;
				}

				//檢驗perfect number
				if(i == sum) {
					perfectNumber[count] = i;
					count++;
				}
			}
			step++;
		}

		if(step == 3) {	//進行"隨機"印出工作
			int random;
			pMark = (int*)malloc(sizeof(int)*(count));	//配置用來標記已經被印出的數字的陣列
			while(countOfPrint < count) {
				random = rand()%count;
				if(*(pMark+random) != 1) {	//如果沒有印過，就先標記再印出
					*(pMark+random) = 1;
					printf("%2d-th perfect number is %d\n", countOfPrint+1, perfectNumber[random]);
					countOfPrint++;
				}
			}
			printf("The perfect number which is less than 10000 have %d(s)\n\n", count);
			step++;
		}

		if(step == 4)	//釋放掉pMark的記憶體
			free(pMark);
	}



	system("pause");
	return 0;
}

#else

//實作動態記憶體

struct perfectNumber {
	int number;
	bool mark;
	perfectNumber *next;
};

int main (int argc, char *argv[]) {

	int choice, step, i, j, sum, count, countOfPrint;
	perfectNumber *pPN, *pPNOfFrist;

	srand(time(NULL));

	while(true) {
		choice = 0, step = 1, count = 0, countOfPrint = 0;	//各種選擇、計數都先歸零
		printf("請選擇\n  (1)進入程式\n  (2)離開程式\n> ");
		fflush(stdin);
		scanf_s("%d", &choice);

		if(choice == 1) {
			step = 2;
			printf("\n");
		} else if(choice == 2) {
			printf("See you!!\n");
			return 0;
		} else
			printf("\n輸入錯誤 請重新輸入\n\n");

		if(step == 2) {	//先把小於10000的prefect number找出來
			pPN = (perfectNumber*)malloc(sizeof(perfectNumber));	//第一個
			pPNOfFrist = pPN;
			for(i = 6;i <= 10000;i++) {
				
				//先計算sum of factor
				sum = 0;	//計算總和前先歸零
				for(j = 1;j < i;j++) {
					if(i%j == 0)
						sum = sum + j;
				}

				//檢驗perfect number
				if(i == sum) {
					pPN->number = i;
					pPN->mark = true;
					pPN->next = (perfectNumber*)malloc(sizeof(perfectNumber));
					pPN = pPN->next;
					count++;
				}
			}
			pPN = pPNOfFrist;	//把位置指回第一個

			//將最後一個元素的next清空
			for(i = 1;i < count;i++)
				pPN = pPN->next;
			pPN->next = NULL;

			pPN = pPNOfFrist;	//再次只回第一個
			step++;
		}

		if(step == 3) {	//進行"隨機"印出工作
			int random;
			while(countOfPrint < count) {
				pPN = pPNOfFrist;	//回歸到第一個
				//處理隨機的問題
				random = rand()%count;
				for(i = 0;i < random;i++)
					pPN = pPN->next;

				if(pPN->mark) {	//如果沒有印過，就先標記再印出
					pPN->mark = false;
					printf("%2d-th perfect number is %d\n", countOfPrint+1, pPN->number);
					countOfPrint++;
				}
			}
			printf("The perfect number which is less than 10000 have %d(s)\n\n", count);
			step++;
		}
	}

	system("pause");
	return 0;
}
#endif