prime generator

[surfersss]

i really want to know whats wrong with this code, it produced "wrong answer" for spoj prime generator. although i tested it and produce correct result
and also how can i optimize this code?


PRIME1 - Prime Generator
#number-theory
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

 #include<iostream>
#include<cstring>
#include <vector>
#include<cstdlib>
#include <cmath>
using namespace std;

void simplesieve(int limit, vector<int>&prime);

void segmentedsieve() {
	int T, M, K;

	cin >> T;
	vector<int> prime;
	simplesieve(35000, prime);

 	for (int t = 0; t < T; t++) {
		cin >> M >> K;
		const int limit = floor(sqrt(K)) + 1;

		bool *mark = new bool[K - M];
		memset(mark, true, sizeof(bool)*(K - M));

		vector<int>::iterator it;

		for (it = prime.begin(); *it < limit; it++) {

			int lolim = floor(M / (*it))*(*it);
			if (lolim < M)
				lolim = lolim + (*it);

			for (int j = lolim; j < K; j += (*it))
			{
				if (j != *it)
					mark[j - M] = false;
			}


		}

		for (int i = M; i < K; i++) {
			if (mark[i - M] == true)
				cout << i << "\n";
		}

		delete[] mark;
	}

}




void simplesieve(int limit, vector<int>&prime) {
/*
	bool *mark = new bool[limit + 1];

	memset(mark, true, sizeof(bool)*(limit + 1));*/
	
	prime.push_back(2);

	for (int i = 3; i < limit; i += 2) {
		bool isprime = true;
		int cap = sqrt(i) + 1;
		vector<int>::iterator it;
		for (it = prime.begin(); it != prime.end(); it++) {
			if (*it >= cap)
			{
				isprime = true;
				break;
			}
			else if ((i%*it )== 0)
			{
				isprime = false;
				break;
			}
		
		 }
		if (isprime) {
			prime.push_back(i);

		}
	}

}


int main()
{
	segmentedsieve();
	return 0;
}

[jonnin]

your sieve seems to work. I hacked in this and got the right answer for the first 100.

void segmentedsieve() {
int T, M, K;

//cin >> T;
vector<int> prime;
simplesieve(100, prime);
for(int dx = 0; dx < prime.size(); dx++)
cout << prime[dx] << endl;
return;


so if you have a problem, its in the segmented function, not your actual primes list.

I got the first 1 billion primes in < 15-20 seconds (my work computer seems to have some background process issues) with just subsequent division method, while the sieve was taking a while to run. I suspect the push-back and such were causing the problems, not the algorithm itself, but you can look at my code in the other thread if that helps.

Get the right answer. then we can make it faster.

[Handy Andy]

Hello surfersss,

Some observations before I get into testing the program.

One thing you will find when writing code is to be consistent with what you do. With the header files I like to do this:

#include<iostream>
#include<cstring>
#include <vector>

#include<cstdlib>
#include <cmath>

using namespace std;  // <--- best not to use. 

Order may not make any difference, but being consistent does help you to remember which header files you need. Normally "cstring" would just be "string". "stdlib.h" id a 50/50 when it comes to including this in a program. Some will say put it in if you think you will need it. And others, like me, will say that it is included somewhere in the "iostream" file.

The "stdio.h" file should be "cstdio" if you use it, but the "iostream" covers this file, so it is not needed.

The first three lines I consider the standard includes, although I include "iomanip" these days, the last two I consider the extras.

The variables "T", "M" and "K". First they should be lowercase letters for a regular variable. The capital letters make me think that they are defined as a constant variable. Also just because "T,M and K" are used in the instructions does not mean that you have to use them. Give them a better name that describes what the variable is or does. This will help you in the future.

When it comes to writing a line like: void segmentedsieve() {. Although it is OK it works better as:

void segmentedsieve()
{
}

This way the {}s line up in the same column. Not only is it easier to read, but it is easier to find the matching brace when they are in the same column. Either way you choose to deal with the {}s be consistent through out the whole program.

I also noticed an extra blank line before some of the closing braces. It is OK, but not needed.

I offer this to help you in the future.

I will see how the program runs shortly.

Hope that helps,

Andy

[Handy Andy]

Hello surfersss,

Something I missed mentioning.

Putting the functions above "main" you really do not need the proto type. The fact that you put it there just means that you should revers the order of the functions.

My personal preference it to use the proto types and put the functions after "main". This tends to keep the top down feel to the way things work with the code.

Andy

[surfersss]

@jonnin
thanks for the answer, yes the simple sieve seems produced correct result, but maybe the wrong partis in segmentedsieve() function, when i try to find multiple of the prime and mark it as not prime inside the range from user input.
is it the part that make it slow?
the time constraint is few seconds maybe 6s, how can i optimize this?
and what make this so slow?

[surfersss]

@Handy Andy
thanks for the observations, i will delete unnecessary part and make it more cleaner

[jonnin]

vector push back can be slow. pre-allocate the space.
creating the iterator outside the loop might help a tiny bit.
your condition is binary. if you default your prime number boolean, you don't have to jump as much.

that is:
isprime = false

code
{
isprime = true
}
//no need for else if to set false, its already false. conditions cost!

stop creating and deleteing mark every iteration. make it once and keep it around, reuse it. Make it the max size it can be instead.

same thing on mark's logic... if its initialized to true or false, you don't need to set it for one of the paths. Binary logic is great. default something, and then only change it for the simpler path of the 2 to reverse your default when its wrong!

ill say it once more. get it working. then make it faster. I can get you the wrong answer instantly :)

[Thomas1965]

@OP,
with what values did you test it ?
What was the output?
When I compiled the code from the first post it didn't compile at all because simplesieve at line 15 is not know at this point.
After I fixed that I trie with the followinf input:
2
1 10
3 5

I didn't get any output.

[thmm]

@OP,
seems you just want solutions and not learning sth. so you could have a look at the solutions at codechef.
https://www.codechef.com/problems/PRIME1

[surfersss]

@Thomas1965 i tested with 1 100 and it produced output, i dont know why you cant get output?

[surfersss]

@jonnin

#include "pch.h"
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include<iostream>
#include<Set>
using namespace std;

void simplesieve(int limit, vector<int>&prime);


void segmentedsieve() {
	int T, M, K;

	cin >> T;
	vector<int> prime;
	simplesieve(32000, prime);

	for (int t = 0; t < T; t++) {
		cin >> M >> K;
		const int limit = floor(sqrt(K)) + 1;


		set<int>notprime;


		vector<int>::iterator it;
		int start;
		for (it = prime.begin(); it != prime.end(); it++) {
			if (*it >= limit)
				break;
			if (*it < M)
				start = floor(M / (*it))*(*it);
			else
				start = (*it) * 2;

			for (int j = start; j < K; j += (*it)) {
				notprime.insert(j);
			}



		}
		for (int o = M; o < K; o++) {
			if (count(notprime.begin(), notprime.end(), o) == 0)
				cout << o << "\n";

		}

	}

}




void simplesieve(int limit, vector<int>&prime) {
	/*
		bool *mark = new bool[limit + 1];

		memset(mark, true, sizeof(bool)*(limit + 1));*/

	prime.push_back(2);

	for (int i = 3; i < limit; i += 2) {
		bool isprime = true;
		int cap = sqrt(i) + 1;
		vector<int>::iterator it;
		for (it = prime.begin(); it != prime.end(); it++) {
			if (*it >= cap)

				break;

			else if ((i%*it) == 0)
			{
				isprime = false;
				break;
			}

		}
		if (isprime) {
			prime.push_back(i);

		}
	}

}


int main()
{
	segmentedsieve();
	return 0;
}

i tried with different way but this seems so slower than first one(?) i delete the mark array

[Thomas1965]

OK, the latest code produces output.
How fast is it ?
How fast should it be ?

EDIT:
I tested the following code on codechef and it passed in 0.92s though a brute force way.
Seems another example where simple easy to write and understand code is good enough.

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

bool is_prime(unsigned int num)
{
  // store calculated primes in case they are checked again
  static std::set<unsigned> primes; 

  if (num <= 1)
    return false;
  else if (num == 2)
    return true;

  if (primes.find(num) != primes.end())
    return true;

  unsigned max_divisor = static_cast<unsigned>(std::sqrt(num));
  for (unsigned i = 2; i <= max_divisor; ++i)
    if (num % i == 0)
      return false;

  primes.insert(num);
  return true;
}

void do_test()
{
  int min_val, max_val;
  
  cin >> min_val >> max_val;
  for (int num = min_val; num <= max_val; ++num)
    if (is_prime(num))
      cout << num << '\n';

  cout << '\n';
}

int main() 
{
  int num_tests;
  cin >> num_tests;

  while(num_tests--)
  {
    do_test();
  }
}

[jonnin]

still pushing back. preallocate and index if you can. or use a different container, as above.

for (it = prime.begin(); it != prime.end() && *it < cap; it++) {
isprime = !((i%*it) == 0); //there is probably a more efficient way to write this expression. Im busy atm.
//if ((i%*it) == 0) <--- move this condition into the loop as well to 'break' (stop looping) when you need to -- I did one of them but not this one and combine the logic if you can.

we are probably polishing a poo here, though. There is something fundamentally wrong if its slow, and making code tuning tweaks won't help until you find and fix that. I don't see it if it isnt the push back problem.

[surfersss]

@Thomas1965
your code seems accepted, but i want to know how to analyse worse case time in your program.

the worse case is when input is 1 billion and have to divide it with i=2- around 10(?)
to find out is it prime or not(?)
is the worse case is o(n)?

for (int num = min_val; num <= max_val; ++num)
    if (is_prime(num))
      cout << num << '\n';

 for (unsigned i = 2; i <= max_divisor; ++i)
    if (num % i == 0)
      return false;

and this if its prime has to iterate i until the number itself
and compare to my code what make my code so slow(?)

[surfersss]

@jonnin
thankyou, but what make my code so slow, is it because i find the prime in simplesieve() and then find prime again in segementedsieve() when finding the prime under the user input number(?)

[Thomas1965]

I don't fully understand your code so I can't say for certain what makes it slow.
My guess is that you have so many loops.
Another problem is that you don't store the primes you have found so it's possible that you calculate them again.

If you want other people to look at your code you should make it more readable by using proper names and add some comments.

[jonnin]

yes, if you find the same prime more than once, that is no good. Fix that first thing.