Algorithm

Problem link- https://www.spoj.com/problems/TDPRIMES/

TDPRIMES - Printing some primes

#sieve-of-eratosthenes

 

The problem statement is really simple. You are to write all primes less than 10^8

Input

There is no input.

Output

To make the problem less output related write out only the 1st, 101st, 201st, ... 1st mod 100.

Example

Input:

Output:
2
547
1229
...
99995257
99996931
99998953

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define INF 1000000000
#define MOD (ll)1000000007
#define pb 	push_back
#define EPS 1e-9
#define FOR(i, n)	for(int i = 0;i  <  n; i++)

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

vector<int> primes;
int maxx = 100000000;
int arr[100000000];

void sieve(){
  arr[0] = 1;
  arr[1] = 1;
  arr[2] = 0;
  primes.pb(2);
  for(int i = 3;i < maxx; i+=2){
      if(arr[i]==0){
          primes.pb(i);
          if(i*(ll)i < (ll)maxx){
              for(int j = i*i; j < maxx; j+=2*i){
                  arr[j] = 1;
              }
          }
      }
  }
}
int main(){
  sieve();
  int i = 0;
  int size = primes.size();
  while(i < size){
      printf("%d\n", primes[i]);
      i+=100;
  }
	return 0;
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
2 547 1229 ... 99995257 99996931 99998953

#2 Code Example with Java Programming

Code - Java Programming

import java.lang.StringBuilder;

final class TDPRIMES{
  public static void main(String args[]){
    StringBuilder sb = new StringBuilder();

    final int MAX_N = 100000000;
    boolean[] is_not_prime = new boolean[MAX_N + 1];
    int no_of_primes = 0;

    sb.append("2\n");
    no_of_primes++;

    for (int p = 3; p*p  < = MAX_N; p += 2){
      if (is_not_prime[p] == false){
        for (int i = p*p; i <= MAX_N; i += p){
          is_not_prime[i] = true;
        }
      }
    }

    for (int p = 3; p <= MAX_N; p += 2){
      if (is_not_prime[p] == false){
        if (no_of_primes++ % 100 == 0){
          sb.append(p);
          sb.append('\n');
        }
      }
    }

    System.out.print(sb.toString());
  }
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
2 547 1229 ... 99995257 99996931 99998953
Advertisements

Demonstration

SPOJ Solution-Printing some primes-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python