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

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