Prime numbers - I need clarification on code implementation-CodePudding

This is the code I know :

bool checkPrime(int n) {
    bool prime = true;

    for (int i = 2; i < n; i  ) {
        if ((n%i) == 0) { 
            prime = false;
        }
    }

    return prime;
}

But is this ok if your looking for prime numbers:

List<int> arr = [2,3,5,7]; // already known
  
int n = 30; // between 1 to 30 it could be any number
  
for (int i = 2; i < n; i  ) {
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0){
        arr.add(i);
    }
    //Then maybe some code for numbers less than 8
}
  
print(arr);

output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

And also is there much difference in time complexity?

CodePudding user response：

Your code is incorrect. This code only works because you are taking the value of n as 30, for a greater number like 1000 this will produce an incorrect result. List arr = [2,3,5,7]; // already known

int n = 1000; // between 1 to 1000 it could be any number
List<int> arr = [2,3,5,7];

for (int i = 2; i < n; i  ) {
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0){
        arr.add(i);
    }
    //Then maybe some code for numbers less than 8
}
  
print(arr);

Your code will return 231 prime numbers when there are actually only 168 prime numbers. This is because you are not considering the future prime numbers that can only be divided by a prime number between 7 to that number.

eg: 121 will be returned by you as prime but it is a multiple of 11

Extending your pattern. Though this will be faster since it has reduced a number of division operations but due to two loops, it will still be N square.

Here I am simply only dividing numbers from the existing prime numbers collection and adding them in the collection if prime is found tobe used in next iteration for division.

  List < int > arr = [2]; // taking 2 since this is the lowerst value we want to start with 
    
    int n = 30; // n can between 2 to any number
    if (n < 3) {
    
        print(arr); // can return from here.
    }
    // since we already have added 2 in the list we start with next number to check that is 3
    for (int i = 3; i < n; i  ) {
        bool isPrime = true;
        for (int j = 0; j < arr.length; j  ) { // we iterate over the current prime number collection only [2] then [2,3]...
            if (i % arr[j] == 0) { // check if number can be divided by exisiting numbers
                isPrime = false;
            }
        }
    
        if (isPrime) { // eg: 2 cant divide 3 so we 3 is also added 
            arr.add(i)
        }
    
    }
    
    print(arr);

You can look a faster pattern here. Which is the fastest algorithm to find prime numbers?