Click here to Skip to main content
15,887,214 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
can anyone help me write this program ? even a pseudo code will do the job.
this program should scan a number like 34 and calculate the largest gap between prime numbers before 34, I mean (29-23-1)=5.
thank you so much

What I have tried:

int y,x,N,large=3,small=2,b,a;
	scanf("%d",&N);

		for(y=3;y<N;++y)
		    for(x=2;x<y;++x)
		        a=y%x;

		if(a==0) break;

		else if(y>large && y>small) small=large;

		large=y;small=x;b=large-small-1;

		if(b<large-small-1)b=large-small-1;

		printf("%d",b);
Posted
Updated 17-Sep-22 2:44am

I would suggest to write a function for the primality test.
For small numbers a naive approach is just enough
C
#include <stdio.h>

unsigned is_prime(unsigned i)
{
  unsigned n;
  for (n=2; n<(i/2+1); ++n)
    if (i%n==0)
      return 0;
  return 1;
}

int main()
{
  unsigned max_gap = 0;
  unsigned max_gap_lower = 0;
  unsigned last_prime = 0;
  unsigned range_limit;

  printf("insert the range upper limit\n");
  if ( scanf("%u", &range_limit) != 1)
    return -1;

  unsigned n;
  for (n=2; n<range_limit; ++n)
  {
    if ( is_prime(n) )
    {
      if ( last_prime )
      {
        unsigned gap = n - last_prime;
        if ( max_gap < gap )
        {
          max_gap = gap;
          max_gap_lower = last_prime;
        }
      }
      last_prime = n;
    }
  }
  if ( max_gap )
  {
    printf("max gap is %u between %u and %u\n", max_gap -1, max_gap_lower, max_gap_lower + max_gap);
  }
  return 0;
}


For bigger numbers you have to choose a more performant algorithm.
 
Share this answer
 
v3
Comments
Rick York 15-Nov-18 10:42am    
For a little more performance, the standard way is to test 2, then 3, and then skip by 2 so it will then test 5, 7, 9, etc. There are still more tests than necessary but half as many as if you don't skip by 2.
CPallini 15-Nov-18 11:58am    
Sure, even the primality test shouldn't run over even numbers, I overlooked it. Fixed now, thanks.
Patrice T 15-Nov-18 12:54pm    
You shouldn't have done this change, now isprime is wrong.
you should check 2 and then start the loop at 3.
CPallini 15-Nov-18 13:02pm    
Yes, you are right. I need definitely more caffeine.
By the way, thank you.
Patrice T 19-Nov-18 15:35pm    
You are welcome.
I know for fact that it is often easier to spot mistakes from others then own mistakes.
You will have to write the program by yourself. But we can share the basic idea. Let's discuss the most easiest way:
1. Make the list of all prime number in the range
2. Get the difference of all prime number
3. Find the max
 
Share this answer
 
No, it's your homework, and we do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think! Start by generating att the prime numbers in the range - that's relatively simple, and probably a task you have done before. Then loop through them, looking for gaps. Keep track of the largest so far, and update it when you find a bigger one. After the loop you have the interval you need.

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!
 
Share this answer
 
Monolithic programs is a bad idea, it just make things more complicated to you. As suggested in S3, making a function handling if a number is a prime or not will simplify the code.
C++
    for(x=2;x<y;++x)
        a=y%x;

if(a==0) break;

Your code don't work, but I get your idea, the code is overkill, to check if 97 is a prime, it will check every number from 2 to 96. When you check by hand, do you stop at 96 or do you stop earlier?
The rule you apply to stop earlier should appear in you code.

The usage of {} matters in C, you should learn to use them as soon as possible.
Quote:
I mean (29-23-1)=5.

Are you sure the gap between 23 and 29 is 5 ?
-----
Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.
Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]
The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
 
Share this answer
 
#include <iostream>
using namespace std;
int prime(int n)
{
   int d=0;
   for(int j=1;j<=n;j++){
       if(n%j==0)
       d++;
   }
   if(d==2)
   return true;
   else
   return false;
    
}
int main()
{
    int doo,gap=0,naj=0,x=0;
    cin>>doo;
    for(int i=1;i<=doo;i++){
        if(prime(i)){
            cout<<i<<" gap is "<<gap<<endl;        
            
            if(naj<gap){
            naj=gap;
            x=i;
                
            }
            gap=1;
        }
        else
        gap++;
        
    }
    cout<<endl<<endl<<"Biggest gap is "<<naj<<"  "<<x;
    return 0;
}
 
Share this answer
 
Comments
Dave Kreskowiak 17-Sep-22 9:55am    
Doing someone's homework for them is never a good idea.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900