fork download
copy 
  1. // cas O(N^2/lg(N))
  2. // PP.size() je asymptoticky N/lg(N), odp.size() asymptoticky N, sito N*lg(N)
  3. #include <cstdio>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int main() {
  8. 	int N,a;
  9. 	scanf(" %d",&N);
  10. 	// zistime pre kazde prvocislo aka najvacsia jeho mocnina je <= N
  11. 	vector<bool> jeP(N+1,true);
  12. 	vector<int> PP; // prime powers
  13. 	// Eratostenovo sito
  14. 	for(int i =2; i <= N; i++) {
  15. 		if(!jeP[i]) continue;
  16. 		a =i;
  17. 		while(a*i <= N) a *=i;
  18. 		PP.push_back(a);
  19. 		for(int j =2; j*i <= N; j++) jeP[j*i] =false;}
  20.  
  21. 	// odpoved je sucin vsetkych tychto max. mocnin
  22. 	vector<int> odp;
  23. 	odp.push_back(1);
  24. 	for(unsigned int i =0; i < PP.size(); i++) {
  25. 		for(unsigned int j =0; j < odp.size(); j++) odp[j] *=PP[i];
  26. 		long long c =0LL; // carry
  27. 		for(unsigned int j =0; j < odp.size(); j++) {
  28. 			c +=odp[j];
  29. 			odp[j] =c%10LL;
  30. 			c /=10LL;}
  31. 		while(c > 0LL) {
  32. 			odp.push_back(c%10LL); 
  33. 			c /=10LL;}}
  34. 	for(int i =odp.size()-1; i >= 0; i--) printf("%d",odp[i]);
  35. 	printf("\n");
  36. 	return 0;}
Success #stdin #stdout 0s 2968KB
comments (?)
stdin
copy 
47
stdout
copy 
442720643463713815200
https://ideone.com/1hDFv
language:
C++14 (gcc 8.3)
created:
12 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!