fork download
  1. #include<stdio.h>
  2. #include<math.h>
  3. #include<string.h>
  4. typedef long long ll;
  5. ll at[1000005];
  6. ll prime(ll n)
  7. {
  8. ll i,count=0;
  9. while(n%2==0)
  10. {
  11. count++;
  12. n=n/2;
  13. }
  14. if(count>at[2])
  15. at[2]=count;
  16. for(i=3;i<=sqrt(n);i=i+2)
  17. {
  18. count=0;
  19. while(n%i==0)
  20. {
  21. count++;
  22. n=n/i;
  23. }
  24. if(count>at[i])
  25. at[i]=count;
  26. }
  27. if(n>2)
  28. {
  29. if(at[n]==0)
  30. at[n]=1;
  31. }
  32. }
  33. int main()
  34. {
  35. ll t,n,i,k,count;
  36. ll ar[100005];
  37. scanf("%lld",&t);
  38. while(t--)
  39. {
  40. for(i=0;i<1000005;i++)
  41. at[i]=0;
  42. count=0;
  43. scanf("%lld",&n);
  44. for(i=0;i<n;i++)
  45. scanf("%lld",&ar[i]);
  46. for(i=0;i<n;i++)
  47. prime(ar[i]);
  48. for(i=0;i<=1000005;i++)
  49. count=count+at[i];
  50. printf("%lld\n",count);
  51. }
  52. return 0;
  53.  
  54. }
Success #stdin #stdout 0s 11928KB
stdin
Standard input is empty
stdout
Standard output is empty