Archive for March, 2009

Project Euler（47）

Posted on Tuesday, March 31st, 2009 at 3:35 pm by Universe Queen

Problem 47:

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

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

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

Answer: 134043

Implementation in Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

public class Euler47 
{
	public static boolean isPrime( int number )
	{
		if( number < 2 )
		{
			return false;
		}
		else if ( number == 2 )
		{
			return true;
		}
		else
		{
			for( long i=2; i<=Math.sqrt(number); i++ )
			{
				if( number%i == 0 )
				{
					return false;
				}
			}
		}
 
		return true;
	}
 
	public static int distinctPrimeFactors( int number )
	{
		int f = 0;
		int p = 2;
		boolean changed = true;
 
		while( !isPrime( number ) )
		{		
			if( number % p == 0 )
			{
				number /= p;
 
				if( changed )
				{
					f++;
				}
 
				changed = false;
			}
			else
			{
				p++;
				changed = true;
			}
		}
 
		f++;
 
		return f;
	}
 
	public static void main(String[] args)
	{
		int result = 647;
 
		while( true )
		{
			if( distinctPrimeFactors(result) == 4 && distinctPrimeFactors(result+1) == 4 && distinctPrimeFactors(result+2) == 4 && distinctPrimeFactors(result+3) == 4 )
			{
				break;
			}
 
			result++;
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 891 Comments »

Project Euler（46）

Posted on Sunday, March 29th, 2009 at 4:43 pm by Universe Queen

Problem 46:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^(2)
15 = 7 + 2×2^(2)
21 = 3 + 2×3^(2)
25 = 7 + 2×3^(2)
27 = 19 + 2×2^(2)
33 = 31 + 2×1^(2)

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Answer: 5777

Implementation in Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

public class Euler46 
{
	public static boolean isPrime( int number )
	{
		if( number < 2 )
		{
			return false;
		}
		else if ( number == 2 )
		{
			return true;
		}
		else
		{
			for( long i=2; i<=Math.sqrt(number); i++ )
			{
				if( number%i == 0 )
				{
					return false;
				}
			}
		}
 
		return true;
	}
 
	public static void main(String[] args)
	{
		int result = 7;
		boolean ok = false;
 
		while( !ok )
		{		
			result += 2;
 
			ok = true;
 
			if( isPrime( result ) )
			{
				ok = false;
				continue;
			}
 
			for( int p=2; p<result; p++ )
			{
				if( isPrime( p ) )
				{
					int r = result - p;
					int k = r / 2;
					double s = Math.round( Math.sqrt(k) );
					s = s * s - k;
 
					if( k*2 == r && s < 0.000001 && s > -0.000001 )
					{
						ok = false;
						break;
					}
				}
			}
		}
 
		System.out.println( result );
	}
}

Tags:
Posted in Project Euler | 675 Comments »