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

E001.m

1000보다 작은 모든 3의 배수 또는 5의 배수의 합.

N까지의 자연수의 합은 N * (N+1) / 2 와 같고,
이 결과에 자연수 A를 곱하면 A*N 까지의 A의 배수의 합이 됩니다.
따라서 1000보다 작은 3의 배수의 합은 999까지를 생각하므로

3 * (999/3 * (999/3 + 1) / 2) 가 됩니다.

999/5는 나누어 떨어지지 않지만, C의 int 타입은 소수점 이런 거 없는 기세넘치는 타입이므로 그냥 버림되고 floor 처리된거와 같습니다.

이 공식으로 3의 배수의 합, 5의 배수의 합을 더한 후 공배수인 15의 배수의 합을 빼면 끝.

E002.m

4백만 이하의 짝수인 피보나치 수열의 항의 합.

피보나치 수열의 일반항을 구하는 공식을 찾기보다는 그냥 루프로 처리.

홀수+짝수 = 홀수
짝수+홀수 = 홀수
홀수+홀수 = 짝수

이므로 피보나치 수열에서 짝수는 3번째마다 등장하고 3N-1항이 짝수가 된다. 이걸 사용해서 루프 한 번 돌 때 세 항씩 진행하는 방법도 있음.

E003.m

매우 큰 어떤 수의 최대 소인수 (600851475143)

코드가 깔끔하진 않아보이는데, 대략 다음과 같은 아이디어 입니다.

1. A가 N의 인수라면 A * B = N 이므로, B도 N의 인수가 됩니다.
2. A가 2일 때부터 생각합니다. 나누어 떨어질 때마다 1씩 더해가면서 검사하다가 딱 나눠떨어지는 순간이 옵니다. 이 때 A는 가장 작은 약수가 되고 B는 가장 큰 약수가 됩니다. 만약 B가 소수라면? 문제에서 묻는 답이 나온 겁니다.
3. 그렇지 않은 경우에는 N = A_a_b_c_.... 과 같이 인수들의 곱으로 표시되므로 B는 A를 제외한 약수의 전체 곱입니다. 즉 B속에 A를 제외한 모든 약수가 존재합니다.
4. 그럼 이 문제는 다시 B의 최대 소인수를 구하는 문제가 되었습니다. A는 2로 시작하면서 1~3의 과정을 반복합니다. 여기서 처음 찾게 되는 소수인 B가 자연스레 최대 B가 됩니다.

소수여부 판별하기

2부터 출발해서 모든 수로 일일이 나눠보는 것도 좋지만, 이정도 문제에서는 이런 방법을 썼다가는 "아 컴퓨터가 ㅈㄴ 느리네" 싶을 수 있습니다. 그래서 가능한 한 계산 횟수를 줄이는 게 좋습니다.

N이 소수인지 여부를 판별하기 위해서는 N까지 갈 필요없이 N의 제곱근까지만 검사를 수행하면 됩니다. 만약 N으로 나누어 떨어지는 A가 발견된다면 A*B = N 일텐데. 이 때 A, B 둘 중 하나는 N의 제곱근보다 크기 때문입니다.(A==B라면 A가 N의 제곱근이 되겠죠) 따라서 N의 제곱근까지만 나누어 떨어지는지를 계산하면 계산 횟수를 많이 줄일 수 있습니다.

또한 루프를 돌 때 2씩 더해서 홀수로만 나눠가면 계산횟수를 다시 절반으로 줄일 수 있게 됩니다.

기타 참고 사항

문제의 수는 32비트 크기를 넘어서는 값입니다. 따라서 int 로는 계산할 수 없고, % 연산자를 쓸 수 없습니다. 코드의 모든 변수는 double 형으로 선언하고 fmod 함수를 사용하여 나머지를 계산해야 합니다.

E004.m

세자리 수 두 개를 곱해 얻을 수 있는 가장 큰 대칭수

처음 작성한 코드는 문자열을 뒤집어서 비교해, 대칭수인지 확인했는데... 이 때 사용한 방법이 NSString의 생성자를 계속 사용하는 방법이었는데 너무 오래걸렸습니다. 결국 C문자열로 다시 변경해서 앞/뒤의 각 문자를 비교하는 방법으로 바꿨습니다.

만약 첫번째 버전과 같이 루프를 돌면서 계속 객체를 생성해야 하면 함수내나 루프 내에 오토릴리즈 풀을 따로 선언해야 메모리 사용량을 줄일 수 있습니다.)

E005.m

1에서 20까지의 모든 자연수로 나누어 떨어지는 수 중 가작 작은 수

1~20의 최소공배수를 구하는 문제. 손으로 최소 공배수를 구하는 방법과 동일한 방식으로 풉니다.

1. 가장 큰 수까지의 모든 소수 리스트를 준비하고
2. 소수들로 각 숫자를 나눠갑니다.
3. 아무런 숫자도 나눠지지 않을 때까지 각 소수로 계속 나눕니다.

각 소수의 나눈 횟수만큼 거듭제곱하여 각 소인수를 곱하면 끝.

범위의 마지막 숫자가 매우 크면 소수 배열을 준비하는데 시간이 많이 걸릴 수 있지만, 그만큼 큰 숫자가 나오면 double 형에 담을 수 없는 결과값을 계산해야 하므로 무시합니다.

• GNUStep의 NSMutableArray에는 기존 원소를 다른 원소로 바꿀 수 있는 메소드가 없어서 카테고리로 추가했습니다.
• 초기에는 C배열을 썼는데, NSArray, NSMutableArray로 바꾸면서 코드 길이가....

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) 과 같이 되도록 하고 있는데, 실제로 중요한 것은 이 들이 몇 번 나오냐는 것이어서 나누어 떨어진 횟수를 별도의 배열에 저장합니다. 실제 약수의 개수는 그 별도 배열만 생각하면 됩니다.