C++

Forum

 
Prime Numbers help in group

Junomaster2006 (15)
I currently need help on separating my Prime numbers in group for my assignment. I absolutely do not know how to do this. I am able to find out if the number I used is prime and see how many prime number there are between 1-100 and then 1-1000 (168 primes) and so on. The thing that I need to do is find the number of prime numbers between 101-200, 201-300, 301-400, and so on until 901-100 and have it show on screen. Here is the exact assignment that I’m supposed to find out:

Assignment:

Write a C++ program to calculate and display the number of primes from 1 to 100,000, separated in groups of 100, 10 groups per line. To be more precise, on the first line of output, display the number of primes between 1 and 100, 101 and 200, etc., up to 901 to 1000. Then display the average primes per group. For example, there are 168 primes from 1 to 1000, so the average number of primes per group of 100 (or percentage) is 16.8. Then repeat the process for the groups of 100 between 1001 to 1100, 1101 to 1200, etc., for all groups of 1000 all the way up to 100,000. Your results should be as presented below, under testing.

Testing:

The output of your program should be the following, according to my calculations. Each group (g1, g2, etc.) is the number of primes in a group of 100 numbers. For example in line 1, g1 is the group from 1 to 100, g2 is the group 101 to 200, etc. For line 2, g1 is the group 1001 to 1100, g2 is 1101 to 1200, and g10 is the group from 1901 to 2000.

g1 g2 g3 g4 g5 g6 g7 g8 g9 g10 Average Primes
----------------------------------------------------------------
25 21 16 16 17 14 16 14 15 14 16.8 for 1 to 1000
16 12 15 11 17 12 15 12 12 13 13.5 for 1001 to 2000
14 10 15 15 10 11 15 14 12 11 12.7 for 2001 to 3000
12 10 11 15 11 14 13 12 11 11 12.0 for 3001 to 4000
…
…
…
7 10 5 10 7 11 7 6 11 8 8.2 for 97001 to 98000
7 5 9 9 11 8 7 8 12 11 8.7 for 98001 to 99000
8 11 8 8 7 9 8 10 10 8 8.7 for 99001 to 100000

Total number of primes from 1 to 100000: 9592
Average primes per 1000: 95.92
Percentage of primes from 1 to 100000: 9.59

Here is my code that I have done so far: 

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
 

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool isPrime(long candidate);
long primeCount (long start, long end);

int main()
{
	int count;
	count = primeCount (1 , 100);
	cout << count << endl;
	system("pause");
	return 0;
}

long primeCount (long start, long end)
{
	bool result;
	long count = 0;
	for(int i = start; i <= end; i++)
	{
		result = isPrime(i);
		if (result == true)
		{
			count++;
		}
	}
	return count;
}

bool isPrime(long candidate)
 {
	bool prime = true;
	if (candidate == 1)
		return false;
	if (candidate == 2)
		return true;
	for (int i =2; i < candidate; i++)
	{
		if (candidate % i == 0)
		{
			prime = false;
			break;
		}	
	}
	return prime;
}


Thank you so much if you can help me with this. I'm just utterly lost what I'm suppose to do now.
geeloso (147)
Your functions seem to be functionally OK; albeit, not efficient from a computer-time perspective. In line 42, there is no need for the loop variable expression to test all the way up to the value of candidate: you just need to test up to around half of the number.

I think you're almost there: just find a way to iteratively present your parameters to function primeCount in function main and do some output formatting.
Junomaster2006 (15)
I showed this code to my instructor and he said everything looks perfectly fine so far. I'm just don't know what to do as a next stepping stone. I understand what I'm suppose to do, but don't know how to code it.
geeloso (147)
Have you tried to run the program to see what's wrong?
ar2007 (210)
ciao,
I would like to propose this solution:
with minor changes in your program is working well.
practically in the "primeCount", you had to enter the parameters that varied with the variation of the while loop.
the results coincide. you just have to format the output on the screen, taking into account that every 10 values ​​of k is a group (0-1000), etc., etc..
you could also use a matrix [10] [100] to sort it, but you should be able the same way.

if you then delete the rest in the search function of prime numbers, and instead uses the Euclidean algorithm, and eliminates the odd multiples of the first, you can greatly increase the speed and extent of your calculation.

ps-I have not included the average of your values ​​.....

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
 
#include <iostream>
#include <string>
#include <math.h>

using namespace std;

bool isPrime(long candidate);
long primeCount (long start, long end);
long k=0;
size_t gruppo[1000]={};

int main()
{
    
    size_t startx=1;
    size_t endx=100;
    while (endx<=100000)
    {
	//long count=0;
    gruppo[k]= primeCount (startx , endx);
	cout <<" gruppo["<<k<<"]= "<< gruppo[k] << endl;
    startx=endx+1;
    endx+=100;
    k++;
    }
	//system("pause");
	return 0;
}

long primeCount (long start, long end)
{
	bool result;
	long count = 0;
	for(long i = start; i <= end; i++)
	{
		result = isPrime(i);
		if (result == true)
		{
			count++;
		}
	}
	return count;
}

bool isPrime(long candidate)
{
	bool prime = true;
	if (candidate == 1)
		return false;
	if (candidate == 2)
		return true;
	for (int i =2; i < candidate; i++)
	{
		if (candidate % i == 0)
		{
			prime = false;
			break;
		}
	}
	return prime;
}
Scorvus (7)
is this the code you looking for? i'm sorry it's very vague
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
65
66
67
68
69
70
71
72
73
74
75
76
77
 
#include<iostream>
#include<stdio.h>
#include<cmath>
float group[10]={0},line[101]={0},sum=0;
bool check(int num)
{
	int flag=0;
	if(sqrt(num)!=int(sqrt(num)))
	{
		for(int i=2;i<=((num/2)+1);i++)
		{
			if(num%i==0)
				flag++;
			if(flag==2)
			{
				return false;
				break;
			}		
		}
	}
	else
		return false;
	if(flag!=2 && sqrt(num)!=int(sqrt(num)))
		return true;
}
void search()
{
	bool isPrime;
	int gr=1,lin=1;
	for(int i=2;i<=100000;i++)
	{
		isPrime=check(i);
		if(isPrime==true)
		{
			group[gr]++;
		}
		if(i%100==0)
		{
			printf("%.0f",group[gr]);
			if(group[gr] < 10)
				printf("  |");
			else
				printf(" |");
			gr++;
		}
		if(i%1000==0)
		{
			gr=1;
			
			for(int j=1;j<=10;j++)
			{
				line[lin]+=group[j];
				group[j]=0;
			}
			printf("%.1f",line[lin]/10);
			if(line[lin]/10<10)
				printf("    ");
			else
				printf("   ");
			printf("for %d to %d\n",i-999,i);
			lin++;			
		}
	}
	for(int i=1;i<=100;i++)
		sum+=line[i];
	printf("Total number of primes from 1 to 100000: %.0f\n",sum);
	printf("Average primes per 1000: %.2f\n",sum/100);
	printf("Percentage of primes from 1 to 100000: %.2f\n",sum/1000);
}

int main()
{
	printf("g1  g2  g3  g4  g5  g6  g7  g8  g9  g10 average\n");
	printf("-----------------------------------------------\n");
	search();
	system("pause");
}
Last edited on
Junomaster2006 (15)
Yes geeloso, the program is able to run.

And for the ar2007 and Scorvus, thanks for the help even though I don't understanding what I'm reading for the first code.
Junomaster2006 (15)
Thank you so much Scorvus. It is not vague and sort of understand the code. I just have no idea what 'printf' means though.
Harsh Saxena (1)
Hey Scorvus, I dont understand one thing in line 12 and 13, if num is divisible by a no. then why not return false right there?
I mean why wait for flag to become 2?
Topic archived. No new replies allowed.