結果

問題 No.12 限定された素数
コンテスト
ユーザー mudbdb
提出日時 2015-06-23 23:32:07
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 70 ms / 5,000 ms
コード長 2,108 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 878 ms
コンパイル使用メモリ 23,040 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-24 08:18:55
合計ジャッジ時間 3,434 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:63:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |   scanf("%d", &N);
      |   ^~~~~~~~~~~~~~~
main.c:65:23: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |   for (i=0; i<N; i++) scanf("%d", &(A[i]));
      |                       ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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