fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 100000001;
  4. int arr[MAX];
  5. vector<bool> vis(MAX, false);
  6.  
  7. void seive() {
  8.     for (int i = 4; i < MAX; i += 2) vis[i] = true;
  9.     for (int i = 3; i * i <MAX; i+=2) {
  10.         if (!vis[i]) {
  11.             for (int j = i * i; j <MAX; j += i) vis[j] = true;
  12.         }
  13.     }
  14.     arr[2] = 1;
  15.  
  16.     for (int i = 3; i < MAX; i +=2) {
  17.         if (!vis[i]) {
  18.             arr[i + 1] = arr[i] = arr[i - 1] + 1;
  19.         }
  20.         else arr[i + 1] = arr[i] = arr[i - 1];
  21.    }
  22.  
  23. }
  24. double calc(int n,int x) {
  25.     double c = (double)n / log(double(n));
  26.     double d= abs((double(x)) - c);
  27.     double ans = (double)d / (double)x;
  28.  
  29.     return ans*100;
  30. }
  31.  
  32.  
  33.  
  34. int main() {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(NULL);
  37.     cout.tie(NULL);
  38.     int test;
  39.     test = 1;
  40.    // cin >> test;
  41.     seive();
  42.     while (1) {
  43.         int n;
  44.         cin >> n;
  45.  
  46.         if (n == 0) break;
  47.         int a = arr[n];
  48.  
  49.  
  50.         printf("%0.1lf\n", calc(n, a));
  51.  
  52.     }
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61. }
Success #stdin #stdout 0.72s 405760KB
comments (?)
stdin
copy 
10000000
2
3
5
1234567
0
stdout
copy 
6.6
188.5
36.5
3.6
7.7
https://ideone.com/QAyx4E
problem CPRIME, based on SPOJ submission 26145938 (CPP14), 2020-06-15 07:51:46
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!