3

In fact my teacher has passed the program that calculates the prime numbers from 1 to N. But I did not understand some things in the code and would like to help.

In line 18 we have the following: for(j=2; j<=i/2; j++), because j was divided by 2? and why j start in 2? should not start i and j on 1?

#include <stdio.h>

int main() {
    int i, j, n, isPrime; //isPrime is used as flag variable

    /* Reads upper limit to print prime */
    printf("Find prime numbers between 1 to : ");
    scanf("%d", &n);

    printf("\nAll prime numbers between 1 to %d are:\n", n);

    /* Finds all Prime numbers between 1 to n */
    for(i=2; i<=n; i++) {
        /* Assume that the current number is Prime */
        isPrime = 1;

        /* Check if the current number i is prime or not */
        for(j=2; j<=i/2; j++) {
            /*
             * If i is divisible by any number other than 1 and self
             * then it is not prime number
             */
            if(i%j==0) {
                isPrime = 0;
                break;
            }
        }

        /* If the number is prime then print */
        if(isPrime==1) {
            printf("%d is Prime number\n", i);
        }
    }

    return 0;
}
Improve this question
1
  • 1
    It's all optimizations. You know every number will divide evenly by 1, and you know every prime (except the first) will not divide by 2. It makes sense to skip those. Commented May 6, 2016 at 16:43

5 Answers 5

Reset to default
2

should not start i ... on 1?

Yes, i should at 1. Consider that the current code will evolve. Later code may look like the below. Notice the comment and code matches your contract "numbers between 1 and N". No implied short-cut starting at 2, but clarity that code is properly testing all numbers [1...N].

/* Finds all Prime numbers between 1 to n */
for(i=1; i<=n; i++) {
  if (IsPrime(i)) {
    printf("%d is Prime number\n", i);
  }
}

The point is that as a programmer, you are given the task "Finding prime number between 1 and N". A common sub-task is to code bool IsPrime(int i). Certainly if you code everything together, i can start at 2 - we know 1 is not a prime. Yet good programming begins with software architecture and that involves divide and conquer. So making a stand-alone helper function that works for all input is a good first step.

should not start j ... on 1?

No. Now code is into its find-a-prime algorithm and starting j=1 would fail.

bool IsPrime(int i) {
  if (i <= 1) return false;  // Cope with negative, 0, and 1.

  for (int j=2; j<=i/2; j++) {
    if (i%j==0) {
      return false;
    }
  }      
  return true;
}

Of course, we can optimize IsPrime() in many ways.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

The first prime number is 2 -- which is why you start as 2 -- everything is divisible by 1, and if you start there your algo will fail.

You end with N/2 because testing larger number will not result in anything that you would not have found, simply because to be a non-prime means that you will have to have to have at least 2 factors, and the smallest prime is 2 and 2*(i/2) >= i -- but in reality it is better and safe to stop at square root of N (but maybe that is in the next lesson).

This starting at 2 and increment the loop by one is wasteful -- since all primes except 2 is odd it would be better to start at 3 and increment by 2, and just make a special test for dividing by 2 outside the loop.

Improve this answer

4 Comments

This code is naive anyway, so there is no point of pointing out it's non-effective moments... There are much better ways to do the same.
While it is true that there are better algos, then giving people pointers to that there is much more to this question that meet the eye is not pointless
Yes, but my point is that there is an infinite number of possible improvements to this. Like skipping every second number. Like skipping every third one, and so on. It's the question where you want to stop "optimizing"
How to optimize this is really a PhD level question, as there are still people trying to find efficient algo's of prime number of astronomical size, since this is key in cryptography)
0

The first prime number is known to be 2, so there is no reason to start with 1. Given number i, there is no reason to try to divide it by numbers greater than its half, as the result will always be less than 2 and yield a quotient of 0 and a non-zero remainder (unless we divide it by itself, which is pointless in the prime test).

Improve this answer

2 Comments

There's no reason to divide by numbers greater than the target's square root.
As I commented to one of the other answers - this is a very naive algorithm, subject to an infinite number of possible optimizations.
0

This is the easiest way:

#include <iostream>
using namespace std;
int main (){
    int first,second;
    cout<<"Enter starting of limit";
    cin>>first;         //First value
    cout<<"Enter Ending of limit";
    cin>>second;    //Second value
    L:
    if(first < second){    //Checking starts here
        if(first % 2 != 0 && first % 5 != 0 || first - 5 == 0 && first % 7 != 0){ 
            cout<<first<<endl;
            first++ ;   
            goto L;     //Iteration
        }
    }
}
Improve this answer

2 Comments

cin, cout and using namespace std are C++ and this question is tagged C. Use printf and scanf instead.
This also isn't going to work, I don't think. It only checks for factors of 2, 5 and 7 and not e.g. 3, 11 or any other primes.
0 
#include<stdio.h>
int main()
{
    int num,i,count,n;
    printf("Enter max range:");
    scanf("%d",&n);

    for(num=1; num<=n; num++)
    {
        count=0;
        for(i=2; i<=num/2; i++)
        {
            if(num%i==0)
            {
                count++;
                break;
            }
        }

        if(count==0 && num!=1)
            printf("%d ",num);
    }
    return 0;
}
Improve this answer

2 Comments

Welcome to Stack Overflow! Please don't answer just with source code. Try to provide a nice description about how your solution works. See: How do I write a good answer?. Thanks
I'm not sure that improves the OP's code that they posted in the question, and in any case I think the OP was asking for an explanation of their own code. So thanks for your answer here but I don't think this really helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.