2010-01-22

3問目。

効率が悪いし、最悪の場合の処理時間がΟ(n^2)。
効率のよい実装をもちょっと考えれるようになりたいです。

#include <iostream>
#include <time.h>

using namespace std;


unsigned int primeCall(unsigned NM){

	unsigned int prime[50000];
	unsigned int box[100000];
	unsigned int p=0;

	for(p=0;p<NM;p++)prime[p]=0;
	prime[0]=2;
	box[0]=0;

	for(p=1;p<=NM;p++)
	{	
		for(int i=prime[p-1];i<10000;i++)
		{
			if((i%prime[p-1])==0)box[i]=0;
			else if (box[i]!=0)box[i]=i;			
		}
		
		for(int i=2;i<10000;i++)
		{
			if(box[i]!=0)
			{
				prime[p]=i;
				break;
			}
		}
	}
	return prime[NM];
}

int main()
{

	unsigned long long int w=600851475143;
	for(int i=0;i<50000;i++){

		if(w==1){
			cout<<"it is finish!"<<endl;
			break;
			}

			while(w%primeCall(i)==0)
			{
			w=w/primeCall(i);
			cout<<primeCall(i)<<endl;
			}

	}
	cout<<"it stopped!"<<endl;
}

2010-01-21

breakにつまづく。

プログラム

深夜にソースを書いちゃダメーっ！
3問目を解こうと、エラトステネスのふるいを実装しようと試みてちょっと挫折気味。

#include <iostream>
#include <time.h>

using namespace std;


int erasto(int NM){

	int n[50];
	int box[100000];
	int ans=0;
	int p=0;

	for(p=0;p<50;p++)n[p]=0;
	n[0]=2;
	box[0]=0;

	for(p=0;p<10;p++)
	{
		for(int i=1;i<100000;i++)
		{
			if((i%n[p])==0) box[i]=0;
			else box[i]=i;
		}
		
		for(int i=0;i<100000;i++)
		{
			if(box[i]!=0)
			{
				n[p+1]=i;		
				break;したい。
			}
		}	
	}
	ans = n[NM];	
	return ans;

}

int main()
{
	cout<<erasto(1)<<endl;
}

2010-01-20

2問目。足りない。。

プログラム Project Euler

未だできてないけど。

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

#include <iostream>
#include <time.h>

using namespace std;

int main()
{
	int l=0;
	int r=1;
	unsigned long int m=0;

	int ans =0;
	
	for(int i=1;i<=4000000;i++){
		m=l+r;
		//cout<<m<<endl;
		if(m%2==0)ans=ans+m;
		l=r;
		r=m;

		
	}
	 cout<<ans<<endl;

}

2010-01-20

■

プログラム Project Euler

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

#include <iostream>
#include <time.h>

using namespace std;

int main()
{

	int n=0;
	for(int i=1;i<1000;i++){
		if(i%3==0||i%5==0){
		n=n+i;
		}
	}
	 cout<<n<<endl;

}