Prime smash!

夏期セミナーで流行ってたiPad用ゲーム
iTunes App Store で見つかる iPad 対応 Panasonic Prime Smash!
id:nikollsonさんとかがよく「素数切らせて」って言ってきましたw
超簡単に言うと、「合成数を切り、素数を取るゲーム」
なんでみんなあんなスコア出せるんだろう？

というわけで、
「素数なら"Prime"と表示し、合成数なら素因数分解する」
プログラムを組んでみた。
imosさんが他の人に教えてたのを横から盗み聞きしたアルゴリズムを使いました。
めちゃくちゃシンプルなので読んだら何やってるのか分かる・・・はず。

#include<cstdio>
#define MAX 1001
using namespace std;

int p[MAX];

int main(){
  int j;
  
  for(int i = 2; i < MAX; i++){
    printf("%d : ",i);
    if(p[i]){
      for(j = i; p[j] != 0; j = j/p[j]){
        printf("%d * ",p[j]);
      }
      printf("%d\n",j);
    } else {
      printf("prime!\n");
      for(j = i*i; j < MAX; j+=i){
        if(!p[j]) p[j] = i;
      }
    }
  }
  return 0;
}

ちょっと違う気がしたので、書き直した。

#include<cstdio>
#define MAX 1001
using namespace std;

int p[MAX];

int main(){
  int j;
  for(int i = 2; i < MAX; i++){
    printf("%d : ",i);
    if(p[i]){
      for(j = i; p[j] != 0; j = j/p[j]){
        printf("%d * ",p[j]);
      }
      printf("%d\n",j);
      for(j = i+p[i]; j < MAX; j+=p[i]){
        if(!p[j]){ p[j] = p[i]; break;}
      }
    } else {
      printf("prime!\n");
      if(i*i < MAX) p[i*i] = i;
    }
  }
  return 0;
}

多分imosさんが言ってたのはこんな感じだったと思う。合ってるかな〜？？？
これだと、素因数が順番通りに表示されない。
メモリアクセスの関係で篩より若干早いらしい。

[2/1追記]なんか違う気しかしないなぁw