結果

問題 No.12 限定された素数
ユーザー mudbdbmudbdb
提出日時 2015-06-23 23:32:07
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 70 ms / 5,000 ms
コード長 2,108 bytes
コンパイル時間 721 ms
コンパイル使用メモリ 26,776 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-15 23:00:18
合計ジャッジ時間 3,618 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
4,376 KB
testcase_01 AC 65 ms
4,380 KB
testcase_02 AC 65 ms
4,376 KB
testcase_03 AC 66 ms
4,376 KB
testcase_04 AC 65 ms
4,376 KB
testcase_05 AC 67 ms
4,376 KB
testcase_06 AC 68 ms
4,380 KB
testcase_07 AC 68 ms
4,376 KB
testcase_08 AC 66 ms
4,380 KB
testcase_09 AC 65 ms
4,380 KB
testcase_10 AC 66 ms
4,380 KB
testcase_11 AC 68 ms
4,376 KB
testcase_12 AC 68 ms
4,380 KB
testcase_13 AC 66 ms
4,376 KB
testcase_14 AC 66 ms
4,380 KB
testcase_15 AC 66 ms
4,380 KB
testcase_16 AC 70 ms
4,380 KB
testcase_17 AC 65 ms
4,376 KB
testcase_18 AC 65 ms
4,376 KB
testcase_19 AC 65 ms
4,376 KB
testcase_20 AC 65 ms
4,380 KB
testcase_21 AC 65 ms
4,376 KB
testcase_22 AC 65 ms
4,376 KB
testcase_23 AC 65 ms
4,380 KB
testcase_24 AC 65 ms
4,380 KB
testcase_25 AC 67 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
int Limit = 5000000;
int IntSize = 32;
int Shift = 5;
int Mask = (1 << 5) - 1;
void bitoff(int *bitfield, int no)
{
  bitfield[no >> Shift] &= (~(1 << (no & Mask)));
  return;
}
int bitget(int *bitfield, int no)
{
  return !(!(bitfield[no >> Shift] & (1 << (no & Mask))));
}
int *Pr = 0;
int Pr_end = 0;
void pr_gen(int limit)
{
  int i, j;
  int fieldblk = ((limit+1)+(IntSize-1))/IntSize;
  int *bitfield = (int*)malloc(sizeof(int)*fieldblk);
  for (i=0; i<fieldblk; i++) bitfield[i] = -1;

  bitoff(bitfield, 0);
  bitoff(bitfield, 1);
  for (i=2; i<=limit; i++) {
    if (1 == bitget(bitfield, i)) {
      Pr_end++;
      for (j=i*2; j<=limit; j+=i) {
        bitoff(bitfield, j);
      }
    }
  }

  Pr = (int*)malloc(sizeof(int)*Pr_end);
  Pr_end = 0;
  for (i=0; i<=limit; i++) {
    if (1 == bitget(bitfield, i)) {
      Pr[Pr_end] = i;
      Pr_end++;
    }
  }
  free(bitfield);
  bitfield = 0;
  return;
}
int Base = 10;
int bitset(int no)
{
  int bit = 0;
  while (no) {
    bit |= (1 << (no % Base));
    no /= Base;
  }
  return bit;
}
int main()
{
  int i;
  int N;
  int *A;
  scanf("%d", &N);
  A = (int*)malloc(sizeof(int)*N);
  for (i=0; i<N; i++) scanf("%d", &(A[i]));

  int cond = 0;
  for (i=0; i<N; i++) cond |= (1 << A[i]);

  if (sizeof(int) != 4) {
    printf("!\n");
    return 1;
  }

  pr_gen(Limit);

  int K, L;
  int bit;
  int max = -1;
  int flag = 0;
  int chkbit = cond;
  int begin, end;
  for (begin=0; begin<Pr_end; ) {
    for (i=begin; i<Pr_end; i++) {
      bit = bitset(Pr[i]);
      if ((~cond) & bit) {
        flag = 1;
        break;
      } else {
        if (chkbit) chkbit &= (~bit);
      }
    }
    if (flag == 1) {
      end = i;
    } else {
      end = Pr_end - 1;
    }
    if (!chkbit) {
      if (begin == 0) {
        K = 1;
      } else {
        K = Pr[begin-1] + 1;
      }
      if (flag == 1) {
        L = Pr[end] - 1;
      } else {
        L = Limit;
      }
      if (max < (L - K)) max = L - K;
    }
    flag = 0;
    chkbit = cond;
    begin = end + 1;
  }

  printf("%d\n", max);
  return 0;
}
0