Project Euler 47 Distinct primes factors（筛法记录不同素因子个数）

题意：

首次出现连续两个数均有两个不同的质因数是在：

14 = 2 × 7
15 = 3 × 5

首次出现连续三个数均有三个不同的质因数是在：

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

首次出现连续四个数均有四个不同的质因数时，其中的第一个数是多少？

方法一：普通筛法

/*************************************************************************

    > File Name: euler047.c

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年06月30日 星期五 15时21分48秒

 ************************************************************************/

#include <stdio.h>

#include <inttypes.h>

#define MAX_N 1000000

int32_t prime[MAX_N + 10] = {0};

int32_t fac[MAX_N + 10]= {0};

void Init() {

	for (int32_t i = 2 ; i < MAX_N ; i ++) {

		if (!prime[i]) {

			for (int32_t j = i ; j < MAX_N ; j += i) {

				prime[j] = i;

				fac[j]++;

			}

		}

	}

}

int32_t main() {

	Init();

	for (int32_t i = 2 ; i < MAX_N ; i++) {

		if ((fac[i] > 3) && (fac[i + 1] > 3) && (fac[i + 2] > 3) && (fac[i + 3] > 3)) {

			printf("ans = %d\n",i);	break;

		}

	}

	return 0;

}

方法二：线性筛

/*************************************************************************

    > File Name: euler047t2.c

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年06月30日 星期五 15时45分48秒

 ************************************************************************/

#include <stdio.h>

#include <inttypes.h>

#define MAX_N 1000000

int32_t prime[MAX_N + 10] = {0};

int32_t facNum[MAX_N + 10] = {0};

void Init() {

	for (int32_t i = 2 ; i < MAX_N ; i++) {

		if (!prime[i]) { prime[ ++prime[0] ] = i; facNum[i] = 1; }

		for (int32_t j = 1 ; j <= prime[0] ; j++) {

			if (i * prime[j] > MAX_N)	break;

			prime[i * prime[j]] = 1;

			if (i % prime[j] == 0) {

				facNum[i * prime[j]] = facNum[i];

				break;

			} else {

				facNum[i * prime[j]] = facNum[i] + 1;

			}

		}

	}

}

int32_t main() {

	Init();

	for (int32_t i = 1 ; i < MAX_N ; i++) {

		if (facNum[i] != 4 )				continue;

		if (facNum[i] != facNum[i + 1])		continue;

		if (facNum[i + 1] != facNum[i + 2])	continue;

		if (facNum[i + 2] != facNum[i + 3])	continue;

		printf("%d\n",i);

		break;

	}

	return 0;

}

巴特西

Project Euler 47 Distinct primes factors（筛法记录不同素因子个数）

最新文章

热门文章

巴特西

Project Euler 47 Distinct primes factors（ 筛法记录不同素因子个数 ）

最新文章

热门文章

Project Euler 47 Distinct primes factors（筛法记录不同素因子个数）