Submission #2473226
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int maxn = 1000010; bool use[maxn]; vector<int> prime,fac[maxn]; void init(){ memset(use,true,sizeof(use)); use[0] = use[1] = 0; for(int i=2;i<=1000000;i++){ if(use[i]){ prime.push_back(i); for(int j = 2*i;j<=1000000;j+=i){ use[j] = false; } } } } int main(){ init(); int l,r; while(cin>>l>>r){ for(int j=0;j<prime.size();j++){ int first = (l-1)/prime[j]*prime[j] + prime[j]; for(int i=first;i<=r;i+=prime[j]){ fac[i-l].push_back(prime[j]); } } int ans = 0; for(int k=l;k<=r;k++){ int num = 0; int t = k; for(int j=0;j<fac[k-l].size();j++){ while(t%fac[k-l][j]==0){ num++;t/=fac[k-l][j]; } } if(t>1) num++; if(use[num]) ans++; fac[k-l].clear(); } cout<<ans<<endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Prime-Factor Prime |
User | cwlyzj |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 922 Byte |
Status | AC |
Exec Time | 393 ms |
Memory | 59000 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 00_sample_05, 10_small_00, 10_small_01, 10_small_02, 10_small_03, 10_small_04, 10_small_05, 10_small_06, 10_small_07, 10_small_08, 10_small_09, 20_medium_00, 20_medium_01, 20_medium_02, 20_medium_03, 20_medium_04, 20_medium_05, 20_medium_06, 20_medium_07, 20_medium_08, 20_medium_09, 30_medium_00, 30_medium_01, 30_medium_02, 30_medium_03, 30_medium_04, 30_medium_05, 30_medium_06, 30_medium_07, 30_medium_08, 30_medium_09, 40_one_00, 40_one_01, 40_one_02, 50_large_low_00, 50_large_low_01, 50_large_low_02, 50_large_low_03, 50_large_low_04, 60_large_high_00, 60_large_high_01, 60_large_high_02, 60_large_high_03, 60_large_high_04, 70_max_low_00, 70_max_low_01, 70_max_low_02, 70_max_low_03, 70_max_low_04, 80_max_high_00, 80_max_high_01, 80_max_high_02, 80_max_high_03, 80_max_high_04 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 17 ms | 25340 KB |
00_sample_01 | AC | 17 ms | 25340 KB |
00_sample_02 | AC | 28 ms | 26744 KB |
00_sample_03 | AC | 17 ms | 25340 KB |
00_sample_04 | AC | 39 ms | 28152 KB |
00_sample_05 | AC | 365 ms | 59000 KB |
10_small_00 | AC | 17 ms | 25340 KB |
10_small_01 | AC | 17 ms | 25340 KB |
10_small_02 | AC | 17 ms | 25340 KB |
10_small_03 | AC | 17 ms | 25340 KB |
10_small_04 | AC | 17 ms | 25340 KB |
10_small_05 | AC | 17 ms | 25340 KB |
10_small_06 | AC | 17 ms | 25340 KB |
10_small_07 | AC | 17 ms | 25340 KB |
10_small_08 | AC | 17 ms | 25340 KB |
10_small_09 | AC | 17 ms | 25340 KB |
20_medium_00 | AC | 50 ms | 29944 KB |
20_medium_01 | AC | 236 ms | 46584 KB |
20_medium_02 | AC | 175 ms | 41848 KB |
20_medium_03 | AC | 87 ms | 34296 KB |
20_medium_04 | AC | 215 ms | 44664 KB |
20_medium_05 | AC | 143 ms | 39544 KB |
20_medium_06 | AC | 294 ms | 53752 KB |
20_medium_07 | AC | 80 ms | 33272 KB |
20_medium_08 | AC | 287 ms | 51960 KB |
20_medium_09 | AC | 36 ms | 27640 KB |
30_medium_00 | AC | 305 ms | 52088 KB |
30_medium_01 | AC | 121 ms | 37496 KB |
30_medium_02 | AC | 202 ms | 44024 KB |
30_medium_03 | AC | 176 ms | 41208 KB |
30_medium_04 | AC | 299 ms | 51192 KB |
30_medium_05 | AC | 165 ms | 41080 KB |
30_medium_06 | AC | 197 ms | 44152 KB |
30_medium_07 | AC | 56 ms | 30328 KB |
30_medium_08 | AC | 73 ms | 32248 KB |
30_medium_09 | AC | 255 ms | 48248 KB |
40_one_00 | AC | 17 ms | 25340 KB |
40_one_01 | AC | 17 ms | 25340 KB |
40_one_02 | AC | 17 ms | 25340 KB |
50_large_low_00 | AC | 368 ms | 55416 KB |
50_large_low_01 | AC | 371 ms | 57080 KB |
50_large_low_02 | AC | 359 ms | 57336 KB |
50_large_low_03 | AC | 360 ms | 57592 KB |
50_large_low_04 | AC | 364 ms | 57720 KB |
60_large_high_00 | AC | 372 ms | 57720 KB |
60_large_high_01 | AC | 364 ms | 57592 KB |
60_large_high_02 | AC | 355 ms | 57336 KB |
60_large_high_03 | AC | 366 ms | 57208 KB |
60_large_high_04 | AC | 364 ms | 56696 KB |
70_max_low_00 | AC | 361 ms | 56952 KB |
70_max_low_01 | AC | 361 ms | 58488 KB |
70_max_low_02 | AC | 367 ms | 58744 KB |
70_max_low_03 | AC | 359 ms | 58872 KB |
70_max_low_04 | AC | 393 ms | 59000 KB |
80_max_high_00 | AC | 366 ms | 59000 KB |
80_max_high_01 | AC | 362 ms | 58872 KB |
80_max_high_02 | AC | 372 ms | 58744 KB |
80_max_high_03 | AC | 363 ms | 58616 KB |
80_max_high_04 | AC | 361 ms | 57976 KB |