素数番目の素数を求めるプログラム

Question

条件

2 は 1 番目の素数であり,3 は 2 番目,5 は 3 番目,7 は 4 番目の素数である。
k 番目の素数 p に対し,k もまた素数である場合に p を「素数番目の素数」と呼ぶことにする.
例えば,3 と 5 は素数番目の素数であり,2 と 7 はそうではない。
整数 n に対し,素数番目の素数であって,n 以下であるものの和を H(n) と定義する。
この時、H(120097839643)を求めよ。
###考え方
素数番目の素数の数え方として素数を数えるプログラムを利用して3重構造の条件式にすれば、
素数番目の素数が数えられるのではないかと考えました。
ただ、このプログラムでは2つ目のflagが必ず1になってしまいます。
しかも、このプログラムでは値がこの条件のように大きくなると重くなってしまいます。
これらを解決する方法が思いつきません。
分かる方いたら回答をお願いします。（つたないプログラムで申し訳ありません)

発生している問題

nを変えても、値がすべて1になってしまいます

該当のソースコード

#include <stdio.h>
#include <math.h>

int h(long long int n)
{
  long long int i,j,k,c=1,flag=0;
  for(i=3;i<=n;i++)
  {
      for(j=3;j<=n;j+=2)
      {
          for(k=3;k<=sqrt(j);k+=2)
          {
                 if(j%k==0)
                 {
                 flag=1;
                 break;
		   	  }
          }
        if(flag==0)
        {
       if(i%j==0)
          {
          flag=1;
          break;
          }
       }
     }
      c++;
   }
  return c;
} 

int main(void){
  printf("%d",h(120097839643));
}

Comments

[Zuishin]

これ、うまく動いたとしても相当時間がかかると思いますが、実行時間制限があるんじゃないですか？

[katkey]

実行時間制限とは何ですか？

[Zuishin]

実行時間があまり長くかかりすぎると不合格ということにはならないかということです。

[katkey]

確かにその通りです。効率よく素数を求められるプログラムをつくりたいのですが…

Answer 1

• 次に欲しい値が何番目の素数か？という値 k を計算する処理(A)
• k 番目の素数を求める処理(B)

の２つの「素数を列挙していく処理」があって，交互に進めていく感じになるのでは．

• 素数列挙処理(A)で k の初期値(=2)を得る．ここで中断．
• 素数列挙処理(B)を進行．2番目の素数を求めた時点で中断
• (A)を再開し，次のkの値(=3)を得る．ここで中断．
• (B)を再開し，3番目の素数を求めた時点で中断

...

みたいな．

Answer 2

回答に至っていないと思いますが・・・。
一度に全てを求め、実装するとややこしいので、まずはとにかく素数を求めるものを作ってみてはいかがでしょうか。
その上で、「素数番目」を考えてみてはいかがでしょう。

素数を求めるだけであればこちらのサイトが参考になるかと思います。

Comments

[Zuishin]

エラトステネスの篩未満で、まったく参考にならないと思いますが。120097839643 までの素数を求めるのに何時間(もしくは何日、もしかしたら何か月)かかるか計測してみてはどうでしょう。