Project Euler : Objc

E001.m

#import <Foundation/Foundation.h>

int main(int argc, char const *argv[])
{
	int i = 3 * (999/3 * (999/3 + 1) / 2) + 5 * ((999/5) * (999/5 + 1) / 2) - 15 * ((999/15) * (999/15 + 1) / 2);
	NSLog(@"%d",i);
	return 0;
}

E002.m

// E002.m

#import <Foundation/Foundation.h>

int main(int argc, char const *argv[])
{
	int a, b, c, sum=0;
	a = 1;
	b = 2;
	while(b <= 4000000) {
		if ( b % 2 == 0) sum += b;
		c = b;
		b += a;
		a = c;
	}
	NSLog(@"%d", sum);
	return 0;
}

//2013-04-17 22:01:43.174 E002[84017:707] 4613732
//[Finished in 0.0s]

E003.m

//E003.m
//600851475143 의 가장 큰 소인수

#import <Foundation/Foundation.h>

BOOL isPrime(double theNum)
{
	if(theNum == 2 || theNum == 3 || theNum == 5 || theNum == 7 || theNum == 11 || theNum == 13) return YES;
	if(fmod(theNum, 2) == 0 || fmod(theNum, 3) == 0 || fmod(theNum, 5) == 0 || fmod(theNum, 7) == 0 || fmod(theNum, 11) == 0) return NO;
	double num, sqrn;
	num = 13;
	sqrn = floor(sqrt(theNum));
	while(num <= sqrn)
	{
		if(fmod(theNum, num) == 0) return NO;
		num += 2;
	}
	return YES;
}


int main(int argc, char const *argv[])
{
	double num = 600851475143;
	double sqrn = ceil(sqrt(num));
	double a=2, b;
	double maxPrime = 2;
	while (a < sqrn) {
		if(fmod(num,a) == 0) {
			b = num / a;
			if(isPrime(b)) {
				maxPrime = b;
				break;
			}
			num = b;
			a = 2;
		}
		a++;
	}

	NSLog(@"%.0f", maxPrime);

	return 0;
}

// 2013-04-17 22:26:19.795 E003[84074:707] 6857
// [Finished in 0.0s]

E004.m

#import <Foundation/Foundation.h>

BOOL isSym(int num)
{
	NSString *numString = [NSString stringWithFormat:@"%i", num];
	const char *cString = [numString UTF8String];
	NSUInteger length = [numString length];
	int i=0;
	while ( i < length/2) {
		if( *(cString+i) != *(cString+length-1-i)) return NO;
		i++;
	}

	return YES;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		int a,b;
		int x, maxSym=0;
		for(a=999;a>=100;a--) {
			for(b=999;b>=100;b--) {
				x = a * b;
				if(isSym(x)) {
					maxSym = (maxSym < x) ? x : maxSym;
				}
			}
		}
		NSLog(@"%d", maxSym);
	}
	return 0;
}

// 2013-04-18 11:49:48.783 E004[4308] 906609
// [Finished in 2.8s]

E005.m

// E005
// LCM of 1...20

#import <Foundation/Foundation.h>

@interface PrimeManager : NSObject
+(BOOL)isPrime:(double)num;
+(NSArray *)primesUpToNumber:(int)num;
@end

@implementation PrimeManager
+(BOOL)isPrime:(double)num{
	if(num == 2 || num == 3 || num == 5 || num == 7 || num == 11) return YES;
	if(!(fmod(num,2) && fmod(num,3) && fmod(num,5) && fmod(num,7) && fmod(num,11))) return NO;
	double a, sqrn;
	sqrn = floor(sqrt(num));
	a = 13;
	while (a <= sqrn) {
		if (fmod(num, a) == 0) return NO;
		a+=2;
	}
	return YES;
}

+(NSArray *)primesUpToNumber:(int)num
{
	NSArray *primes;
	@autoreleasepool {
		NSMutableArray *array = [NSMutableArray array];
		int i=2;
		while (i <= num)
		{
			if([self isPrime:i])
			{
				[array addObject:@(i)];
			}
			i = (i ==2 ) ? i + 1 : i + 2;
		}
		primes = [array copy];
	}
	return [primes autorelease];
}
@end


/*
	There is no -setObject:atIndexedSubscript: in GNUStep's NSMutableArray,
	Add such a method with category.
*/

@interface NSMutableArray (replaceObject)
-(void)setObject:(id)object atIndex:(NSUInteger)idx;
@end
@implementation NSMutableArray (replaceObject)
-(void)setObject:(id)object atIndex:(NSUInteger)idx
{
	if(idx >= [self count] || [self count] == 0) {
		[self addObject:object];
		return;
	}
	[self removeObjectAtIndex:idx];
	[self insertObject:object atIndex:idx];
}
@end

NSMutableArray *arrayOfRange(NSUInteger start, NSUInteger length)
{
	NSMutableArray *range = [NSMutableArray array];
	NSUInteger i=0;
	while(i<length) {
		[range addObject:@(start + i)];
		i++;
	}
	return range;
}



int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSUInteger numberCount = 20, primeIndex=0;
		NSMutableArray *numbers = arrayOfRange(1,numberCount);
		NSMutableArray *exps = [NSMutableArray array];
		int i; 
		for(i=0;i<numberCount;i++) { [exps addObject:@0];}

		NSArray *primes = [PrimeManager primesUpToNumber:numberCount];
		BOOL completed, divided = NO;
		completed = NO;
		while (!completed) {
			for(i=0;i<numberCount;i++) {
				if( [[numbers objectAtIndex:i] intValue] % [[primes objectAtIndex:primeIndex] intValue] == 0)
				{
					if(divided == NO) {
						divided = YES;
						[exps setObject:@([[exps objectAtIndex:primeIndex] intValue] + 1) atIndex:primeIndex];
					}

					[numbers setObject:@([[numbers objectAtIndex:i] intValue] / [[primes objectAtIndex:primeIndex] intValue])
						atIndex:i];
				}
			}
			if(divided) {
				divided = NO;
			} else {
				primeIndex++;
				if(primeIndex == [primes count]) completed = YES;
			}
		}

		double LCM = 1;
		for(primeIndex=0;primeIndex < [primes count]; primeIndex++) {
			LCM *= pow([[primes objectAtIndex:primeIndex] intValue], [[exps objectAtIndex:primeIndex] intValue]);
		}

		NSLog(@"%.0f", LCM);
	}
	return 0;
}

// 2013-04-18 14:24:41.813 E005[8648] 232792560
// [Finished in 0.4s]

E006.m

// sum of square and squar of sum
// sum of square => N * (N+1) * (2N+1) / 6
// square of sum => N*N*(N+1)*(N+1)/4

#import <Foundation/Foundation.h>
int main(int argc, char const *argv[])
{
	int m = 100;
	NSLog(@"%i", abs((m*(m+1)*(2*m+1)/6) - (m*m*(m+1)*(m+1)/4)));
	return 0;
}
// 2013-04-18 15:25:36.650 E006[7116] 25164150
// [Finished in 0.5s]

E007.m

// 10001th Prime Number
#import <Foundation/Foundation.h>

@interface PrimeFinder : NSObject
{
	NSMutableArray *_primes;
}
-(NSUInteger)numberOfPrimes;
-(void)addPrime;
@end
@implementation PrimeFinder
-(NSMutableArray*)primes
{
	if(!_primes) {
		_primes = [[NSMutableArray alloc] init];
		[_primes addObjectsFromArray:@[@2, @3, @5, @7, @11, @13, @17, @19]];
	}
	return _primes;
}

-(void)addPrime
{
	double temp = [[self.primes lastObject] doubleValue] + 2;
	double sqrn = sqrt(temp);
	BOOL found = NO;
	int i=0;
	double test;
	while(!found) {	
		test = [[self.primes objectAtIndex:i] doubleValue];
		if(test > sqrn) {
			found = YES;
			[self.primes addObject:@(temp)];
		}
		else if(fmod(temp, test) == 0) {
			temp += 2;
			sqrn = sqrt(temp);
			i=0;
		}
		i++;
	}

}

-(NSUInteger)numberOfPrimes
{
	return [self.primes count];
}

-(void)dealloc
{
	[_primes release];
	[super dealloc];
}

@end


int main(int argc, char const *argv[])
{
	@autoreleasepool {
		PrimeFinder *p = [[PrimeFinder alloc] init];
		while([p numberOfPrimes] < 10001) {
			[p addPrime];
		}
		NSLog(@"%.0f", [[p.primes lastObject] doubleValue]);
		[p release];
	}
	return 0;
}

// 2013-04-18 17:08:21.158 E007[7972] 104743
// [Finished in 0.4s]

E008.m

#define kSAMPLE_NUMBER @"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
#import <Foundation/Foundation.h>

NSUInteger getMultipliedValue(NSString *string)
{
	NSUInteger len = [string length];
	NSUInteger i, m=1;
	for(i=0;i<len;i++) {
		unichar c = [string characterAtIndex:i];
		m *= (c-48);
		// ^ '1' == 49
	}
	return m;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSString *values = kSAMPLE_NUMBER;
		NSString *substring;
		NSRange range;
		NSUInteger start=0, length=5, maxValue=0, temp;
		while(start + 5 < [values length]) {
			range = NSMakeRange(start, length);
			substring = [values substringWithRange:range];
			temp = getMultipliedValue(substring);
			maxValue = (maxValue < temp) ? temp : maxValue;
			start++;
		}
		NSLog(@"%i", maxValue);
	}
	return 0;
}


// 2013-04-18 18:01:00.482 E008[8868] 40824
// [Finished in 0.5s]

E009.m

#import <Foundation/Foundation.h>

int main(int argc, char const *argv[])
{
	int a,b,c;
	for(a=1;a<333;a++) {
		for(b=a+1;b<(999-a/2);b++) {
			c = 1000 - b - a;
			if( a*a + b*b  == c*c) {
				NSLog(@"%d", a*b*c);
				b = 1000; a =1000;
			}
		}
	}
	return 0;
}

// 2013-04-18 19:04:47.078 E009[7972] 31875000
// [Finished in 0.8s]


// @another solution
// (8, 15, 17) --> 8^2 + 15^2 = 17^2;  8+15+17=40 ---> 1000 / 25
// so, a, b, c = 8*25, 15*25, 17*25

E010.m

// sum of all prime numbers less than 2,000,000
#import <Foundation/Foundation.h>

/* Reuse PrimeFinder from E007*/
@interface PrimeFinder : NSObject
{
	NSMutableArray *_primes;
}
-(NSUInteger)numberOfPrimes;
-(void)addPrime;
@end
@implementation PrimeFinder
-(NSMutableArray*)primes
{
	if(!_primes) {
		_primes = [[NSMutableArray alloc] init];
		[_primes addObjectsFromArray:@[@2, @3, @5, @7, @11, @13, @17, @19]];
	}
	return _primes;
}

-(void)addPrime
{
	double temp = [[self.primes lastObject] doubleValue] + 2;
	double sqrn = sqrt(temp);
	BOOL found = NO;
	int i=0;
	double test;
	while(!found) {	
		test = [[self.primes objectAtIndex:i] doubleValue];
		if(test > sqrn) {
			found = YES;
			[self.primes addObject:@(temp)];
		}
		else if(fmod(temp, test) == 0) {
			temp += 2;
			sqrn = sqrt(temp);
			i=0;
		}
		i++;
	}

}

-(NSUInteger)numberOfPrimes
{
	return [self.primes count];
}

-(void)dealloc
{
	[_primes release];
	[super dealloc];
}

@end


int main(int argc, char const *argv[])
{
	@autoreleasepool {
		PrimeFinder *p = [[PrimeFinder alloc] init];
		while([[p.primes lastObject] intValue] < 2000000) {
			[p addPrime];
		}
		if([[p.primes lastObject] doubleValue] > 2000000) [p.primes removeLastObject];
		double sum=0;
		for(NSNumber *num in p.primes) {
			sum += [num doubleValue];
		}

		NSLog(@"%.0f", sum);
		[p release];
	}
	return 0;
}

// 2013-04-18 19:16:13.630 E010[3320] 142913828922
// [Finished in 3.6s]

E011.m

// Maximum Multiplied value of 4 numbers out of grid.
// compiled with ARC

#import <Foundation/Foundation.h>

NSArray *parseToArray10x10(NSString *string)
{
	NSArray *array;
	@autoreleasepool {
		NSMutableArray *rows = [NSMutableArray array];
		NSUInteger start=0, length=3;
		NSRange range;
		int i,j;
		for(i=0;i<20;i++) {
			NSMutableArray *row = [NSMutableArray array];
			for(j=0;j<20;j++) {
				range = NSMakeRange(start, length);
				NSString *aNumber = [string substringWithRange:range];
				NSNumber *aNum = @([aNumber intValue]);
				[row addObject:aNum];
				start += 3;
			}
			[rows addObject:row];
		}
		array = [rows copy];
	}
	return array;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSString *grid = @"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 ";
		NSArray *nums = parseToArray10x10(grid);

		// 가로방향의 최대합을 구해보자
		int i,j;
		int k;
		double maxM=0, tempM;
		for(i=0;i<20;i++) {
			NSArray *row = [nums objectAtIndex:i];
			for(j=0;j<17;j++) {
				tempM = 1;
				for(k=0;k<4;k++) {
					tempM *= [[row objectAtIndex:(j+k)] intValue];
				}
				maxM = (tempM > maxM) ? tempM : maxM;
			}
		}

		// 세로 방향의 최대합
		for(i=0;i<20;i++) {
			for(j=0;j<17;j++) {
				tempM = 1;
				for(k=0;k<4;k++) {
					tempM *= [[[nums objectAtIndex:j+k] objectAtIndex:i ] intValue];
				}
				maxM = (tempM > maxM) ? tempM : maxM;
			}
		}

		// 오른쪽 대각선
		for(i=0;i<17;i++){
			for(j=0;j<17;j++) {
				tempM=1;
				for(k=0;k<4;k++) {
					tempM *= [[[nums objectAtIndex:i+k] objectAtIndex:j+k] intValue];
				}
				maxM = (tempM > maxM) ? tempM : maxM;
			}
		}
		

		// 왼쪽 대각선
		for(i=0;i<17;i++){
			for(j=3;j<20;j++) {
				tempM=1;
				for(k=0;k<4;k++) {
					tempM *= [[[nums objectAtIndex:i+k] objectAtIndex:j-k] intValue];
				}
				maxM = (tempM > maxM) ? tempM : maxM;
			}
		}


		NSLog(@"%3.0f", maxM);
		}


	return 0;
}
// 2013-04-18 23:31:55.687 E011[85951:707] 51267216
// [Finished in 0.0s]

E012.m

// 500개 이상의 약수를 갖는 삼각수

#import <Foundation/Foundation.h>


@interface PrimeDivisor : NSObject
{
	NSMutableArray *primeFactors, *exps, *primes;
	double value;
}
-(NSUInteger)numberOfPrimeFactors;
@property (assign) double value;
@end

@interface PrimeDivisor ()
-(void)factorize;
-(void)addNextPrime;
@end

@implementation PrimeDivisor
@synthesize value;
-(id)init
{
	self = [super init];
	if(self) {
		primeFactors = [[NSMutableArray alloc] init];
		exps = [[NSMutableArray alloc] init];
		primes = [[NSMutableArray alloc] init];
		[primes addObjectsFromArray:@[@2, @3, @5, @7, @11, @13, @17, @19]];
	}
	return self;
}

-(void)dealloc
{
	[primeFactors release];
	[primes release];
	[exps release];
	[super dealloc];
}

-(void)addNextPrime
{
	double temp = [[primes lastObject] doubleValue] + 2;
	double sqrv;
	BOOL found = NO;
	while(!found)
	{
		sqrv = sqrt(temp);
		for(NSNumber* num in primes) {
			if([num doubleValue] > sqrv) {
				found = YES;
				break;
			}
			else if (fmod(temp, [num doubleValue])==0) {
				temp += 2;
				break;
			}
		}
	}
	[primes addObject:@(temp)];
}

-(void)factorize
{
	@autoreleasepool{
		double aPrime, sqrv=sqrt(value);
		double temp = value;
		BOOL divided=NO, completed=NO;
		NSUInteger primeIndex=0, primeCount=0;
		[primeFactors removeAllObjects];
		[exps removeAllObjects];
		while([[primes lastObject] doubleValue] < sqrv) {
			[self addNextPrime];
		}

		while(!completed) {
			aPrime = [[primes objectAtIndex:primeIndex] doubleValue];
			if(fmod(temp, aPrime) == 0) {
				[primeFactors addObject:@(aPrime)];
				primeCount ++;
				temp = temp / aPrime;
			} else {
				primeIndex++;
				[exps addObject:@(primeCount)];
				primeCount = 0;
				if(primeIndex >= [primes count]) completed = YES;
			}
			if(temp < aPrime) {
				[exps addObject:@(primeCount)];
				completed = YES;
			}
		}
	}
}

-(NSUInteger)numberOfPrimes
{
	return [primes count];
}

-(NSUInteger)numberOfPrimeFactors {
	if(value ==1 ) return 1;
	[self factorize];
	NSUInteger number = 1;
	for(NSNumber *num in exps) {
		number *= (1 + [num intValue]);
	}

	return number;
}
@end

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		PrimeDivisor *p = [[PrimeDivisor alloc] init];
		double num;
		double i=1;
		BOOL found = NO;
		while(!found) {
			num = i * (i + 1) / 2;
			[p setValue:num];
			if([p numberOfPrimeFactors] >= 500) {
				NSLog(@"%.0f", num);
				found = YES;
			}
			i++;
		}
		[p release];
	}
	return 0;
}

// 2013-04-19 10:57:38.777 E012[1620] 76576500
// [Finished in 0.9s]

PrimeDivisor.m

// 소인수분해
#import <Foundation/Foundation.h>


@interface PrimeDivisor : NSObject
{
	NSMutableArray *primeFactors, *exps, *primes;
	double value;
}
@property (assign, nonatomic) double value;
-(NSUInteger)numberOfPrimeFactors;
-(double)sumOfAllFactors;
@end

@interface PrimeDivisor ()
-(void)factorize;
-(void)addNextPrime;
-(NSArray*)uniquePrimeFactors;
@end

@implementation PrimeDivisor
@synthesize value;
-(id)init
{
	self = [super init];
	if(self) {
		primeFactors = [[NSMutableArray alloc] init];
		exps = [[NSMutableArray alloc] init];
		primes = [[NSMutableArray alloc] init];
		[primes addObjectsFromArray:@[@2, @3, @5, @7, @11, @13, @17, @19]];
	}
	return self;
}

-(void)dealloc
{
	[primeFactors release];
	[primes release];
	[exps release];
	[super dealloc];
}

-(void)setValue:(double)newValue
{
	value = newValue;
	[self factorize];
}

-(void)addNextPrime
{
	double temp = [[primes lastObject] doubleValue] + 2;
	double sqrv;
	BOOL found = NO;
	while(!found)
	{
		sqrv = sqrt(temp);
		for(NSNumber* num in primes) {
			if([num doubleValue] > sqrv) {
				found = YES;
				break;
			}
			else if (fmod(temp, [num doubleValue])==0) {
				temp += 2;
				break;
			}
		}
	}
	[primes addObject:@(temp)];
}

-(void)factorize
{
	@autoreleasepool{
		double aPrime, sqrv=sqrt(value);
		double temp = value;
		BOOL divided=NO, completed=NO;
		NSUInteger primeIndex=0, primeCount=0;
		[primeFactors removeAllObjects];
		[exps removeAllObjects];
		while([[primes lastObject] doubleValue] < sqrv) {
			[self addNextPrime];
		}

		while(!completed) {
			aPrime = [[primes objectAtIndex:primeIndex] doubleValue];
			if(fmod(temp, aPrime) == 0) {
				[primeFactors addObject:@(aPrime)];
				primeCount ++;
				temp = temp / aPrime;
			} else {
				primeIndex++;
				[exps addObject:@(primeCount)];
				primeCount = 0;
				if(primeIndex >= [primes count]) completed = YES;
			}
			if(temp < aPrime) {
				[exps addObject:@(primeCount)];
				completed = YES;
			}
		}
	}
}

-(NSUInteger)numberOfPrimes
{
	return [primes count];
}

-(NSUInteger)numberOfPrimeFactors {
	if(value ==1 ) return 1;
	NSUInteger number = 1;
	for(NSNumber *num in exps) {
		number *= (1 + [num intValue]);
	}

	return number;
}

-(NSArray*)uniquePrimeFactors
{
	NSArray *result;
	@autoreleasepool {
		NSMutableArray *uniquePrimeFactors = [NSMutableArray array];
		NSUInteger count = 0;
		for(id num in primeFactors) {
			if(![uniquePrimeFactors containsObject:num]) [uniquePrimeFactors addObject:num];
		}
		result = [uniquePrimeFactors copy];
	}
	return [result autorelease];
}

-(double)sumOfAllFactors
{
	double result=1;
	@autoreleasepool {
		NSMutableArray *sums = [NSMutableArray array];
		NSArray *uPrimes = [self uniquePrimeFactors];
		NSLog(@"%@", uPrimes);
		double aSum=0;
		int i, count;
		for(i=0; i<[uPrimes count];i++) {
			for(count=0; count < [[exps objectAtIndex:i] intValue] +1; count++) {
				aSum += pow([[uPrimes objectAtIndex:i] intValue], count);
			}
			[sums addObject:@(aSum)];
		}

		for(NSNumber *sum in sums) {
			result *= [sum intValue];
		}
	}
	return result;
}
@end

E006.m

제곱수의 합 구하는 공식은 N * (2N + 1) * (N+1) / 6 이므로 이를 사용해서 바로 계산합니다.

제곱수의 합 역시 아주 큰 값은 아니므로 루프를 돌며 계산해도 됩니다.

E007.m

이전 문제에서 사용했던 isPrime: 함수는 거의 모든 홀수에 대해서 나눠보느라 (비록 N의 제곱근까지만 검사를 수행해서 계산 횟수를 많이 줄였지만) 계산량이 많습니다. 이 방법을 사용해서 10001번재 소수를 찾으면 시간이 꽤 걸립니다.

만약 N이 소수가 아니라면 N의 제곱근 n 이하의 자연수로 나눌 때 나눠지는 수가 있게 마련입니다. 그리고 그러한 수에는 소수가 반드시 있습니다.

결국 N이 소수인지 판별하는 가장 좋은 방법은 N의 제곱근 n 이하의 모든 소수에 대해서 N이 나누어 떨어지는지 검사하면 됩니다. 나누어 떨어지는 소수가 없다면 N도 소수입니다.

n보다 작은 소수를 반복적으로 찾아서 배열에 집어넣고, 이 값들만으로 검사해서 다음 소수를 계속 찾아나가는 방법으로 검사하면 소수를 빨리 찾을 수 있습니다. 물론 숫자가 훨씬 더 커지면 다음 소수를 찾아내는데는 점점 더 많은 시간이 걸리기 때문에 다시 다른 방법을 찾아야 할 겁니다.

E008.m

이 문제는 결국 문자로 표시되는 숫자('1')를 수로 전환하여 계산할 수 있는가를 묻는다고 볼 수 있습니다. 제시된 숫자를 문자열로 만들고 NSString의 -substringWithRange:를 사용하여 일부를 추출합니다. 5자리 숫자로 된 문자열의 각 자리 값은 -characterAtIndex:를 통해 구할 수 있는데, 이는 '1'이라는 글자이고 이 글자를 나타내는 수는 49입니다. 결국 코드값에 48을 빼면 숫자가 가리키는 수가 되고 이 값을 곱해주면 됩니다.

E009.m

A+B+C=1000 이 되는 피타고라스 수 A,B,C에 대해 A_B_C를 구하시오 (A<B<C)

A^2 + B^2 = C^2 이고
C = 1000 - A - B 이므로
이 두 식으로 비교해서 값을 찾습니다. 여기서는 A<B<C임을 생각하면 A는 333보다는 작은 수여야하고 B는 A보다는 큰 수라는 점을 이용하면 루프의 횟수를 조금이라도 줄일 수 있습니다.

E010.m

2백만 이하의 모든 소수의 합

E070.m에서 만든 PrimeFinder를 재활용합니다. 구해진 소수들은 NSArray에 담겨있고, 이 배열은 for (... in ...) 구문을 통해 _fast-enumeration_을 사용해 합계를 구했습니다.

E011.m

20X20 격자에 배치된 숫자들에서 특정 방향으로 연속한 4숫자의 곱.

연속으로 배치된 문자열을 가지고 20개씩 20번 나눠서 숫자값으로 바꿔 2차원 배열을 만듭니다. (NSArray로 하려니 좀 어려웠네요) 그런다음에는 각 인덱스를 잘 생각해보면 쉽습니다.

곱을 담을 변수는 1로 초기화해야 합니다. 0으로 초기화하면.... 흠..

E012.m

약수의 개수가 500개 이상인 가장 작은 삼각수

삼각수는 1부터 연속한 자연수의 합이 되는 숫자입니다. 이는 연속된 자연수의 합이므로 삼각수의 일반항은 n * (n+1) / 2로 구할 수 있습니다. (가우스 오빠 고마워요)

약수의 개수를 구하려면 이 숫자들을 모두 소인수 분해해야 합니다. 소인수 분해하고 각 소인수의 지수에 1씩 더해서 이 값들을 모두 곱하면 약수의 개수가 나옵니다. 예를 들어 어떤 자연수 N이 다음과 같이 소인수 분해 된다고 할 때

N = A^a * B^b * C^c .... (A,B,C는 소수)

약수의 개수는 (a+1) * (b+1) * (c+1) 처럼 됩니다.

여기서는 소인부 분해의 결과가 (2,2,2,2,3,3) 과 같이 되도록 하고 있는데, 실제로 중요한 것은 이 들이 몇 번 나오냐는 것이어서 나누어 떨어진 횟수를 별도의 배열에 저장합니다. 실제 약수의 개수는 그 별도 배열만 생각하면 됩니다.