fork(1) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. bool contains(int n, std::vector<int> &v){
  7.     if(find(v.begin(), v.end(), n) != v.end()){
  8.         return true;
  9.     }
  10.     return false;
  11. }
  12.  
  13. std::vector<int> getPrimes(int n){
  14.  
  15.     bool isPrime[n];
  16.     std::fill(isPrime, isPrime+n+1, true);
  17.  
  18.     for (int i = 4; i < n; i+=2) {
  19.         isPrime[i] = false;
  20.     }
  21.  
  22.     for(int i=3, j=i*i; j <= n; i+=2){
  23.         if(isPrime[i]){
  24.             for(; j <= n; j+=2*i){
  25.                 isPrime[j] = false;
  26.             }
  27.         }
  28.     }
  29.     std::vector<int> ret;
  30.     ret.push_back(2);
  31.     for(int i = 3; i<=n; i+=2){
  32.         if(isPrime[i]){
  33.             ret.push_back(i);
  34.         }
  35.     }
  36.     return ret;
  37. }
  38.  
  39. void factorize(int n, std::vector<int> &primes){
  40.  
  41.     for(int prime: primes){
  42.         if( n < prime || contains(n, primes) ){
  43.             break;
  44.         }
  45.         while(n%prime==0){
  46.             std::cout << prime;
  47.             n /= prime;
  48.             if(n==1){
  49.                 return;
  50.             }
  51.             std::cout << "*";
  52.         }
  53.     }
  54.     std::cout << n;
  55.     return;
  56. }
  57.  
  58. int main()
  59. {
  60.     std::ios_base::sync_with_stdio(false);
  61.     std::vector<int> primes = getPrimes((int)sqrt(8000000));
  62.     int n, number;
  63.     std::cin >> n;
  64.     for(int i=0; i<n; i++){
  65.         std::cin >> number;
  66.         if(number==1){
  67.             std::cout << 1;
  68.             continue;
  69.         }
  70.         factorize(number, primes);
  71.     }
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
00
https://ideone.com/jwQPwI
language:
C++ (gcc 8.3)
created:
5 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!