包除原理っぽいもの。

てきとーに書いた。間違ってる可能性大。
包除原理をさっきまで知らなかったんだけど、

|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

集合Tの個数を|T|として、和集合の大きさを計算すること。たぶん。

10^8未満の素数2,3,5,7,11,13,17,19,23,29の倍数の個数を数えるプログラムを書いた。
集合関係に持ち込めばアルゴリズムとして十分応用可能だなぁ。

#include <stdio.h>
main()
{
	int i,j,k,c;
	long long MAX = 100000000LL;	//1e8
	long long ans = 0;
	const int num[]={2,3,5,7,11,13,17,19,23,29};
	const int size = sizeof(num)/sizeof(num[0]);
	
	for(i=1;i<(1<<size);i++){
		long long m = 1;
		for(j=1,c=k=0;j<=i;j<<=1,c++){
			if(i&j){
				m *= num[c];
				k++;
			}
		}
		long long p = (MAX-1)/m;
		ans += p*(k&1?1:-1);
	}
	printf("ans:%lld\n",ans);
	return 0;
}

あ、明けましておめでとうございます。