gamegame's blog

By gamegame, history, 6 years ago, In English

Problem source (Traditional Chinese): https://tioj.ck.tp.edu.tw/problems/2073

Basically, the problem asks to write a program to check whether the T<=5000 numbers (<=1e9) are prime. Moreover, your program must be in C++ and fits the following format:

#include <cstdio>

bool IsPrime(int n) {
  int r=1___f_____r__f___f____n___=0__%__f);
  return_____4_n__;
}

int main() {
  int x;
  while (~scanf("%d", &x)) printf("%d\n", (int)IsPrime(x));
}

You can edit each '_' with any character with ASCII code between 32 to 126.

I have tried to solve this problem for a long time and couldn't solve it. I have created a "solution", but it only works without -O2 optimization. Link: https://pastebin.com/K9sCXXn2

I desperately wanted to know the solution to this problem. Can somebody drop hints or solutions to this problem? Thanks!

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gamegame (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Looking at other people's runtime we can guess that solutions are either "fast" (takes time = smallest factor for composite number) or "slow" (always take time √n or √MAX_N).

I only have a "slow" solution. These are some hints:

  • Declare a variable named f
  • Contains a for loop
  • Contains a ,
  • Contains a &
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have found a solution! For those who are curious: https://pastebin.com/D38nbWik

I think many solutions exist. I would like to hear about different approaches as well.