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
AC × 59
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