fork download
copy 
  1. #include<stdio.h>
  2. int pa[5000001];
  3. void inil(){
  4.     int i,j;
  5.     for(i=2;i<=5000000;i++){
  6.         if(pa[i]==0){
  7.             pa[i]=i;
  8.             for(j=i;j<=5000000/i;j++){
  9.                 if(pa[i*j]==0){
  10.                     pa[i*j]=i;
  11.                 }
  12.             }
  13.         }
  14.     }
  15. j=1;
  16. int cnt=0;
  17. for(i=5000000;i>=2;i--){
  18. if(pa[i]!=i&&pa[i]>j){
  19. j=pa[i];
  20. //printf("%d -> %d\n",i,j);
  21. }
  22. if(pa[i]!=i&&pa[i]>500)cnt++;
  23. }
  24. printf("%d\n",cnt);
  25. }
  26. int main(){
  27.     inil();
  28.     int t;
  29.     scanf("%d",&t);
  30.     while(t--){
  31.         int n;
  32.         scanf("%d",&n);
  33.         while(n>1){
  34.             int k=pa[n];
  35.             n/=k;
  36.             printf("%d ",k);
  37.         }
  38.         printf("\n");
  39.     }
  40. }
Success #stdin #stdout 0.1s 21160KB
comments (?)
stdin
copy 
1
4789
stdout
copy 
90620
4789
https://ideone.com/XvYdGh
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

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!