// so.cpp
#include <Windows.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <time.h>

#define MAX_SO 0x8000000
unsigned long long int getnextso(unsigned long long int num, BOOL tsuzuki);
BOOL isso(unsigned long long int num);
unsigned long long int* lso1 = NULL;
unsigned long long int* lso2 = NULL;

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

	lso1 = (unsigned long long int*)malloc(MAX_SO * sizeof(unsigned long long int));
	lso2 = (unsigned long long int*)malloc(MAX_SO * sizeof(unsigned long long int));

	unsigned long long int n = (unsigned long long int)10000UL;
	while (1) {
		printf("整数を入力して下さい。（終了するときは0):");
		scanf_s("%lld", &n);
		if (!n)break;
		_strtime_s(tmpbuf, 128);
		printf("%s Start\n", tmpbuf, n);
		if (!isso(n)) {
			_strtime_s(tmpbuf, 128);
			printf("%s %lld は素数ではありません。\n", tmpbuf, n);
		}
		else {
			_strtime_s(tmpbuf, 128);
			printf("%s %lld は素数です。\n", tmpbuf, n);
		}
		printf("次の素数は %lld です。\n", n = getnextso(n, FALSE));
		for (int i = 0; i < 10; i++) {
			printf("次の素数は %lld です。\n", n = getnextso(n, TRUE));
		}
	}
	free(lso1);
	free(lso2);
	return 0;
}

BOOL isso(unsigned long long int num)
{
	char tmpbuf[128];
	lso1[0] = 2;

	if (num < 2) return FALSE;

	if (num < 4) return TRUE;

	for (unsigned long long int i = 1; i < MAX_SO; i++) {
		lso1[i] = lso1[i - 1] + 1;
		while (1) {
			for (int j = 0; j < i; j++) {
				if (num == lso1[i] * lso1[j]) {
					return FALSE;
				}
				if (lso1[i] % lso1[j] == 0) {
					lso1[i]++;
					break;
				}
				if (lso1[j] * lso1[j] > lso1[i]) {
					_strtime_s(tmpbuf, 128);
					if ((i + 1) % 1000000 == 0) {
						printf("%s %lld 個目の素数は %lld です。\n", tmpbuf, i + 1, lso1[i]);
					}
					goto _NEXT;
				}
			}
		}
	_NEXT:
		if (num == lso1[i])
			return TRUE;
	}

	return FALSE;
}

unsigned long long int getnextso(unsigned long long int num, BOOL tsuzuki)
{
	static unsigned long long int first = 1;
	if (tsuzuki == FALSE)
		first = 1;
	lso2[0] = 2;

	for (unsigned long long int i = first; i < MAX_SO; i++) {
		lso2[i] = lso2[i - 1] + 1;
		while (1) {
			for (int j = 0; j < i; j++) {
				if (lso2[i] % lso2[j] == 0) {
					lso2[i]++;
					break;
				}
				if (lso2[j] * lso2[j] > lso2[i]) {
					//					printf("%d, ", lso2[i]);
					if (num < lso2[i - 1]) {
						first = i;
						return lso2[i - 1];
					}
					else if (num == lso2[i - 1]) {
						first = i + 1;
						return lso2[i];
					}
					goto _NEXT;
				}
			}
		}
	_NEXT:
		;
	}

	return 0;
}