これはObjective-Cを学習するためにProjectEulerの問題を解いていこうという思いつきだけで始まったいつまで続くかわからない企画である。
Problem 3 「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
あのさ…素因数ってなんだったっけ？？？
素因数とは
素因数（そいんすう、英: prime factor）は、自然数の内、ある自然数の約数になる素数である。ある数の素因数を求めてその積の形で表すことを素因数分解という。例えば60は 22×3×5 と素因数分解されるので60の素因数は 2,3,5 の3つである。また、7は素数であるため素因数分解できず、7の素因数は7自身のみとなる。
素因数 - Wikipedia
素数とは
１とその数(以下nとする)以外で割り切れない数。
素数 - Wikipedia
要するに
6 = 2 × 3
8 = 2 × 2 × 2
15 = 3 × 5
33 = 3 × 11
みたいな感じですね。
なので
前回の要領で、とりあえず素数を返すジェネレータ的なクラスを作ってみよう！
|＼○ﾋｬｯ ε=＼＿○ﾉ ﾎｰｳ!!
PrimeNumberクラス
前回のコメント欄で教えて頂いたNSEnumeratorを使っちゃうよ！
プロパティ
なし
コンストラクタ
- init :初期化。nextObjectすると永遠に素数を返す。
- initWithLimit :nextObjectすると指定した数まで素数を返す。
メソッド
- nextObject :値を次に更新する(同時に更新した素数を返す)
静的メソッド
- (BOOL)isPrime: :素数判定
- prime_factorization :引数を素因数分解して配列に入れる
ロジック
素数判定には色んな方法があるようですが、今回は最も単純だと思われる総当たりで判定しようと思います。
nを1を超える数（つまり２）からn未満の数で割ってみて、途中で割り切れたら素数ではない、最後まで割り切れなかったら素数である、という方法で。
nの平方根を超える数字で検証するのはムダらしいけど(∩ﾟдﾟ)ｱｰｱｰきこえなーい！
#import <Foundation/Foundation.h>
@interface PrimeNumbers : NSEnumerator
{
@protected int _num,_limit;//@protectedはサブクラスからも利用できる
bool _loop;//宣言しない場合は@protectedになる
}
-(id)initWithLimit:(int)limit;
+(BOOL)isPrime:(int)number;//素数判定
+(id)prime_factorization:(int)value;//素因数分解
@end
#import "PrimeNumbers.h"
@implementation PrimeNumbers
-(id)init{
if (self = [super init]) {
_num = 2;
_limit = 0;
_loop = YES;
}
return self;
}
-(id)initWithLimit:(int)limit{
if (self = [self init]) {
_limit = limit;
_loop = NO;
}
return self;
}
+(BOOL)isPrime:(int)number{
for (int i=2; i<number; i++) {
if (number % i == 0) {
return NO;
}
}
return YES;
}
-(id)nextObject{
while (_loop || _num < _limit) {//次の素数を発見するまでループ
int n = _num;
_num++;
if ([PrimeNumbers isPrime:n]) {
return @(n);//intのままではidとしてreturnできないのでキャストする。
}
}
return nil;
}
+(id)prime_factorization:(int)value{//素因数分解
NSMutableArray *arr =[NSMutableArray array];
PrimeNumbers *primes = [[PrimeNumbers alloc]init];
NSNumber *x =[primes nextObject];
while (value != 1) {
if (value%x.intValue==0) {
[arr addObject:x];
value = value / x.intValue;
}else{
x = [primes nextObject];
}
}
return arr;
}
@end
今回覚えたワザ
.hで変数を宣言する時にスコープを設定できる。
@private : クラス内からのみ参照可能
@protected : privateに加えてサブクラスからも参照可能
@public : どこからでも参照可能
※省略した場合は@protectedになる。
※@packageというのもあるみたいだけど特殊らしいので割愛しました。
親クラスのメソッドをオーバーライドする場合はヘッダファイルで宣言しなくてもいい
今回で言えばinitとnextObjectですね。
考えてみたら当たり前ですね。
静的なメソッド(staticメソッド)の宣言方法
javaなら
static void hoge()
Objective-Cでは
+(void)hoge
つまり先頭が「+」ならstaticメソッド、「-」ならインスタンスメソッドです。
回答
上記のクラスを使ったらもうカンタン。
NSLog(@"%@",[[PrimeNumbers prime_factorization:600851475143]lastObject]);
//2013-05-05 13:52:59.256 Euler[598:303] 6857