carmichael number

ViewController.mm

//
//  ViewController.mm
//  CarmichaelNumber
//
//  Created by MizushimaYusuke on 8/31/15.
//  Copyright (c) 2015 MizushimaYusuke. All rights reserved.
//

#import "ViewController.h"
#include <vector>
#include <memory>
using namespace std;

class CarmichaelNumber {
public:
    vector<int> find(int n) {
        vector<int> numbers;
        for (uint64_t i=3; i<=n; i++) {
            BOOL isCarmichaelNumber = true;
            for (uint64_t j=2; j<i; j++) {
                if (modpow(j, i, i) != (j % i) || isPrime((int)i)) {
                    isCarmichaelNumber = false;
                    break;
                }
            }
            if (isCarmichaelNumber) numbers.emplace_back(i);
        }
        return numbers;
    }
private:
    template <typename T>
    T modpow(T base, T exp, T mod) {
        T res = 1;
        while (exp > 0) {
            if (exp & 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }
    bool isPrime(int n) {
        for (int i=2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return n != 1;
    }
};

@interface ViewController ()
@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    self.view.backgroundColor = [UIColor darkGrayColor];
    
    UIView *rView = [[UIView alloc] initWithFrame:CGRectMake(0, 0, CGRectGetMidX(self.view.bounds), CGRectGetMaxY(self.view.bounds))];
    rView.backgroundColor = [UIColor colorWithHue:0 saturation:0.65 brightness:0.7 alpha:1];
    [self.view addSubview:rView];
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    shared_ptr<CarmichaelNumber> cppClass(new CarmichaelNumber());
    vector<int> res = cppClass->find(4000);
    
    [self show:res to:4000];
}

- (void)show:(vector<int>)numbers to:(int)to{
    
    if (to == 0)
        return;
    
    UILabel *l = [[UILabel alloc] init];
    l.font = [UIFont systemFontOfSize:30];
    l.textColor = [UIColor whiteColor];
    l.text = [NSString stringWithFormat:@"%d", to];
    [l sizeToFit];
    l.center = CGPointMake(CGRectGetMidX(self.view.bounds) * 0.5, -50);
    [self.view addSubview:l];

    
    if(find(numbers.begin(), numbers.end(), to) != numbers.end()) {
        [UIView animateKeyframesWithDuration:0.1 delay:0 options:UIViewKeyframeAnimationOptionCalculationModeLinear animations:^{
            l.center = CGPointMake(l.center.x, numbers.size() * 100);
        } completion:^(BOOL finished) {
            [UIView animateWithDuration:0.1 animations:^{
                l.center = CGPointMake(l.center.x * 3, numbers.size() * 100);
            }];
        }];
        
        numbers.erase(find(numbers.begin(), numbers.end(), to));
        
    } else {
        [UIView animateKeyframesWithDuration:0.2 delay:0 options:UIViewKeyframeAnimationOptionCalculationModeLinear animations:^{
            l.center = CGPointMake(l.center.x, 800);
        } completion:^(BOOL finished) {
            [l removeFromSuperview];
        }];
    }
    

    
    dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(0.001 * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
        [self show:numbers to:to - 1];
    });
}

@end