Advertisement
momo2345

prime printing

Nov 3rd, 2020
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace __gnu_pbds;
  6. typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
  7. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define endl "\n"
  9. #define mn int main()
  10. #define frac() cout.unsetf(ios::floatfield);cout.precision(6);cout.setf(ios::fixed,ios::floatfield);
  11.  
  12. /*const int mx=1e6+123;
  13. bool isprime[mx];
  14. vector<int>prime;
  15. void primegen(int n)
  16. {
  17.     memset(isprime, 1,sizeof(isprime));
  18.     isprime[1]=0;
  19.     for(int i=2;i<=n;i++){
  20.         for(int j=i*2;j<=n;j+=i)   //O(n*ln(n))
  21.             isprime[j]=0;
  22.     }
  23.     for(int i=2;i<=n;i++){
  24.         if (isprime[i]) prime.push_back(i);
  25.     }
  26. }
  27.  
  28. mn
  29. {
  30.     suni;
  31.     int n; cin>>n;
  32.     primegen(n);
  33.     for(auto u:prime) cout<<u<<" ";
  34.     cout<<endl;
  35. }*/
  36.  
  37.  
  38. /*const int mx=1e6+123;
  39. bool isprime[mx];
  40. vector<int>prime;
  41. void primegen(int n)
  42. {
  43.     memset(isprime, 1,sizeof(isprime));
  44.     isprime[1]=0;
  45.     for(int i=2;i<=n;i++){
  46.             if(isprime[i]){
  47.         for(int j=i*2;j<=n;j+=i)
  48.             isprime[j]=0;
  49.       }
  50.     }
  51.     for(int i=2;i<=n;i++){
  52.         if (isprime[i]) prime.push_back(i);
  53.     }
  54. }
  55.  
  56. mn
  57. {
  58.     suni;
  59.     int n; cin>>n;
  60.     primegen(n);
  61.     for(auto u:prime) cout<<u<<" ";
  62.     cout<<endl;
  63. }*/
  64.  
  65. /*const int mx=1e6+123;
  66. bool isprime[mx];
  67. vector<int>prime;
  68. void primegen(int n)
  69. {
  70.     memset(isprime, 1,sizeof(isprime));
  71.     isprime[1]=0;
  72.     for(int i=3;i<=n;i+=2){
  73.             if(isprime[i]){
  74.         for(int j=i*2;j<=n;j+=i)
  75.             isprime[j]=0;
  76.       }
  77.     }
  78.     prime.push_back(2);
  79.     for(int i=3;i<=n;i+=2){
  80.         if (isprime[i]) prime.push_back(i);
  81.     }
  82. }
  83.  
  84. mn
  85. {
  86.     suni;
  87.     int n; cin>>n;
  88.     primegen(n);
  89.     for(auto u:prime) cout<<u<<" ";
  90.     cout<<endl;
  91. }*/
  92.  
  93.  
  94. //seieve algo of generating prime
  95. const int mx=1e8+123;
  96. bool isprime[mx];
  97. vector<int>prime;
  98. void primegen(int n)
  99. {
  100.    for(int i=3;i<=n;i+=2) isprime[i]=1;
  101.     for(int i=3;i*i<=n;i+=2){
  102.             if(isprime[i]){
  103.         for(int j=i*i;j<=n;j+=(i*2))
  104.             isprime[j]=0;
  105.       }
  106.     }
  107.     isprime[2]=1;
  108.     prime.push_back(2);
  109.     for(int i=3;i<=n;i+=2){
  110.         if (isprime[i]) prime.push_back(i);
  111.     }
  112. }
  113.  
  114. mn
  115. {
  116.     suni;
  117.     primegen(1e8);
  118.     for(int i=0;i<prime.size();i+=100) cout<<prime[i]<<endl;
  119. }
  120.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement