C++

Forum

 
Prime Numbers

xxvms (197)
Hi there

I am trying to finish prime number code,
the idea is that user provide number how many numbers should be checked if they are prime numbers, then loop fills vector with numbers.
Once vector is filled, I run check if number is prime and I want to print this number.

I am not sure but somehow I am making mistake and my statement(s) don't work in a way I would expect.
I am using modulo operator, 1st I am checking if number is smaller then 2, if it is smaller then 2 is not prime number, then I am checking if modulo return 0. However, when I test 20 there are leftover = 0 for 2, 5 and 10. where as 23 is not always showing. Where is my mistake?

I am sorry about messy code at this stage(I was trying to put this in function then I playing and testing various solutions with no luck so far.
thanks :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
// PrimeNumbers.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>

//void isPrime(std::vector<int>&, int*);

int main()
{
	int HowMany = 0;
	int* HowManyPointer = &HowMany;
	std::cout << "How many prime numbers do you want?" << std::endl;
	std::cin >> HowMany;
	std::vector<int>PrimeNumberVector;
	std::vector<int>PrimeNumberVectorModulo;

	for (int i = 0, j = 20; i < HowMany; j++, i++)
	{
		PrimeNumberVector.push_back(j); // creating vector to store numbers to be checked if they are prime numbers
		//std::cout << "1st loop: " << PrimeNumberVector[i] << std::endl;
	}

	for (unsigned int i = 2; i < PrimeNumberVector.size(); i++) //
	{

		for (unsigned int j = 2; j < PrimeNumberVector.size()+1; j++)
		{
			if (2 > PrimeNumberVector[i]) //prime number must be bigger then 1
			{
				std::cout << "\t Not prime number Smaller then 2 " << PrimeNumberVector[i] << std::endl;
			}

			else if (PrimeNumberVector[i] % j == 0)
			{
				//std::cout << "J: " << j << std::endl;

				continue;
			}
			else (PrimeNumberVectorModulo.push_back(PrimeNumberVector[i]));
			
		}
			
	}
		for (unsigned int i = 0; i < PrimeNumberVectorModulo.size(); i++)
		{
			std::cout << "Modulo: " << PrimeNumberVectorModulo[i]+1 <<  std::endl;
		}
	//isPrime(PrimeNumberVector, HowManyPointer); // call to function

	system("pause");
	return 0;
}

	
void isPrime(std::vector<int>& PrimeNumberVector, int* HowManyPointer)
{

	

}
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
#include <vector>
#include <cmath>

// return true if number is a prime number (simple trial division)
bool is_prime( int number )
{
    if( number < 2 ) return false ;
    if( number == 2 ) return true ; // 2 is a prime number
    if( number%2 == 0 ) return false ; // even numbers other than 2 are not prime

    const int ub_root = std::sqrt(number) + 1.5 ; // upper bound on the square root of the number

    // trial division by odd numbers from three up to (including) the square root of the number
    for( int divisor = 3 ; divisor < ub_root ; divisor += 2 )
        if( number%divisor == 0 ) return false ; // evenly divisible; not prime

    return true ;
}

// return the count of prime numbers in the input vector
std::size_t how_many_prims( const std::vector<int>& numbers )
{
    std::size_t count = 0 ;

    // http://www.stroustrup.com/C++11FAQ.html#for
    for( int n : numbers ) // for each number in the vector
        if( is_prime(n) ) ++count ;

    return count ;
}

// return a sequence prime numbers present in the input vector
std::vector<int> prime_numbers_in( const std::vector<int>& numbers )
{
    std::vector<int> result ;

    for( int n : numbers ) // for each number in the vector
        if( is_prime(n) ) result.push_back(n) ;

    return result ;
}

int main()
{
    const std::vector<int> data_set { 100, 101, 102, 103, 105, 107, 108, 109, 111, 113,
                                      122, 127, 131, 135, 139, 141, 149, 150, 151, 158 } ;

    const std::vector<int> primes = prime_numbers_in(data_set) ;

    std::cout << "list of prime numbers in the data set:\n" ;
    // http://www.stroustrup.com/C++11FAQ.html#for
    for( int n : primes ) std::cout << n << ' ' ;
    std::cout << "\nthere are #" << primes.size() << " prime numbers in the data set\n" ;
}
closed account (48T7M4Gy)
If you want to get the prime numbers in the range between two numbers and the Sieve of Eratosthenes is to your liking. It's easily adaptable to vectors.

The principle is get all the primes up to the higher number and filter out the results for the prime numbers below the lower.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
#include <iostream>

int main(){
    
    int higher = 0, lower = 0;
    
    std::cout << "Enter lower and higher numbers:\n";
    std::cin >> lower >> higher;
    
    
    uint64_t limit = higher;
    
    int* sieve = new int[limit]();
    
    for ( uint64_t i = 2; i * i < limit; i++)
        if (sieve[i] == 0)
            for (uint64_t j = i + i; j < limit; j += i)
                sieve[j] = 1;
    
    for ( uint64_t j = lower; j < higher; j++)
    {
        if (sieve[j] == 0)
            std::cout << j << ' ';
    }
    
    std::cout << '\n';
    
    return 0;
}
Enter lower and higher numbers:
1000 1101
1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 
Program ended with exit code: 0
xxvms (197)
Hi JBlogers

thank you for the code. Lets see if I understand this ;)
my comments in bold.

so in order to fix my code I should add
if( number%2 == 0 ) return false ;
const int ub_root = std::sqrt(number) + 1.5 ;
and
for( int divisor = 3 ; divisor < ub_root ; divisor += 2 )
if( number%divisor == 0 ) return false ; // evenly divisible; not prime

or do i still miss something?

thank you for your help :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 

#include <iostream> 
#include <vector>
#include <cmath>

// return true if number is a prime number (simple trial division)
bool is_prime( int number )
{
    if( number < 2 ) return false ; // if number is smaller then true 
    if( number == 2 ) return true ; // 2 is a prime number 
    if( number%2 == 0 ) return false ; // even numbers other than 2 are not prime

    const int ub_root = std::sqrt(number) + 1.5 ; // upper bound on the square root of the number  I have seen people using sqrt but I don't understand why do you add + 1.5? 

    // trial division by odd numbers from three up to (including) the square root of the number
    for( int divisor = 3 ; divisor < ub_root ; divisor += 2 )
        if( number%divisor == 0 ) return false ; // evenly divisible; not prime
// so if number returns something else then 0 would that be prime number then?

    return true ;
}

// return the count of prime numbers in the input vector
std::size_t how_many_prims( const std::vector<int>& numbers ) //  this is just counter for prime numbers as i understand
{
    std::size_t count = 0 ;

    // http://www.stroustrup.com/C++11FAQ.html#for
    for( int n : numbers ) // for each number in the vector
        if( is_prime(n) ) ++count ;

    return count ;
}

// return a sequence prime numbers present in the input vector 
// printing constant numbers 
std::vector<int> prime_numbers_in( const std::vector<int>& numbers )
{
    std::vector<int> result ;

    for( int n : numbers ) // for each number in the vector
        if( is_prime(n) ) result.push_back(n) ;

    return result ;
}

int main()
{
    const std::vector<int> data_set { 100, 101, 102, 103, 105, 107, 108, 109, 111, 113,
                                      122, 127, 131, 135, 139, 141, 149, 150, 151, 158 } ;
// this is vector with numbers to check

    const std::vector<int> primes = prime_numbers_in(data_set) ; [b] in this line you are sending numbers to check (data_set)

    std::cout << "list of prime numbers in the data set:\n" ;
    // http://www.stroustrup.com/C++11FAQ.html#for
    for( int n : primes ) std::cout << n << ' ' ;
    std::cout << "\nthere are #" << primes.size() << " prime numbers in the data set\n" ;
}

xxvms (197)
Hi Kemort

thank you for the code and suggestions :)
your code looks much easier to process at lest for me.
I have to try to figure out what this part of the code does

uint64_t limit = higher;

int* sieve = new int[limit]();

for ( uint64_t i = 2; i * i < limit; i++)

I didn't use before unit64_t so I am guessing this is a type (like int)
then you create pointer sieve and dynamically assign memory for an array???

all my previous exercises where based on array, now Mr Stroustrup introduced vector :) so I will try to acomplish what i did with vector.

same question as for JBlogers (not sure if he will have time to answer (or you)) do I have to correct my statements as I listed in previous post?

thank you again for you time and help :)
closed account (48T7M4Gy)
Hi xxvms,

I adapted a small program I wrote recently to demonstrate this other approach and uint64_t is a carry over from that. It extends the range of int, see http://www.cplusplus.com/reference/cstdint/ You can use int if you like but the range won't be so great.

You're right the int* etc creates a dynamic array because the extent of the array is not known until the user inputs a value for higher.

With the for statement it is only necessary to check factors up to the square root of the particular number so i*i is a convenient way of avoiding the sqrt() function and the associated extra #include.

<vectors> are designed to be functionally far superior to simple arrays like all the containers, and everybody hammers that point. You need to know both and why. <string>'s vs char[], char* is the same situation. Try using <vector>'s instead. You still have to declare the vector but it eliminates the dynamic array aspect.

https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes, might also be of interest :)
JLBorges (13770)
> so in order to fix my code I should add 
1
2
 
> if( number%2 == 0 ) return false ;
> const int ub_root = std::sqrt(number) + 1.5 ;

and 
1
2
 
> for( int divisor = 3 ; divisor < ub_root ; divisor += 2 )
> if( number%divisor == 0 ) return false ; // evenly divisible; not prime

> or do i still miss something?

It is not a "fix"; it makes the trial division faster.

For instance to check if 156 is a prime number,
instead of performing trial division by every number 2, 3, 4, 5, 6 .... 152, 153, 154, 155
now we do that only for the numbers 3, 5, 7, 9, 11

The even divisors were already taken care of by checking if 156 was even,

and the square root of 156 is 12.xxx, so we do not need to check divisibility by numbers above 13
ie. if 156 == a * b, and a is greater than or equal to 13, then b must be less than 13.



> I don't understand why do you add + 1.5

When a floating point number is narrowed to an integer, the rounding is towards zero.

If the number is, say, 169, std::sqrt(169) may return 12.9999999999 (floating point computations are not exact).

A +0.5 would ensure that we get 13 as the value when we narrow it to an integer.

Another +1.0 is merely to enable us to write the loop as canonical loop
(write the loop condition as divisor < ub_root instead of divisor <= root)
boost lexical cast (395)
@JLBorges

In your code, the function std::size_t how_many_prims(const std::vector<int>&) isn't used. Is it there just to show how it was done for the benefit of the OP? Also, just wondering, isn't std::vector<int>::size_type more appropriate than std::size_t here?
Last edited on
JLBorges (13770)
> Is it there just to show how it was done for the benefit of the OP?

Yes.


> isn't std::vector<int>::size_type more appropriate than std::size_t here?

If the container was templated on the allocator, certainly std::vector<int,ALLOCATOR>::size_type would be correct (more appropriate).

If the use of the default allocator is hard-coded, std::size_t is perfectly fine; in practice, std::vector<int>::size_type would be a type alias for std::size_t.
xxvms (197)
Hi JLBorges

thanks for such great explanation :) I will put a side time to implement this in to my code (and make it work!!! :D)

Topic archived. No new replies allowed.