How do you separate prime numbers from a list in python?

I have a list of numbers [7, 9, 11, 13, 15, 20, 23] and I need to create a list of Prime numbers from given list.

I have written below code but this results 9 & 15 as prime too. I am not getting what I am missing here.

a = [7, 9, 11, 13, 15, 20, 23] 

x = []
for i in range (0, len(a)):
    num = a[i]
    for m in range (2,num):
        if (num % m)==0:
            break
        else:
            print('This is prime', num)
            x.insert(i, num)
            break

I Expect the output list x as [7, 11, 13, 23].

A guide on how to print a list of prime numbers using Python.

As I am continuously striving to expand my knowledge of programming in Python, I have decided to try my hand at creating algorithms. As a result, I have found some questions that one can be asked at a coding interview. One such question is to print out the prime numbers from a range of numbers.

Prime numbers are special numbers, greater than 1, that have exactly two factors, themselves and 1.The prime numbers below 20 are: 2, 3, 5, 7, 11, 13, 17, 19. Don’t forget: the number 1 is not a prime number as it only has one factor.

Since the general rule of thumb is that one is not a prime number, it cannot be included in the printout of prime numbers that is generated by the function.

The pseudocode that I have written, with the help of the StackOverflow website, can be found below:

1. The variables, lower and upper, which give the values of the upper and lower bands of the prime numbers to be printed are defined.
2. The method, print_prime, is defined. This method accepts the variables, upper and lower, as input.
3. The empty list, prime_list, is defined.
4. A for loop is created to iterate through the lower value and the upper value plus 1.
5. The variable, prime, is set to True.
6. If num is 1 then prime is sent to False (because 1 is not considered a prime number).
7. Another for loop is created where i iterates through the numbers 2 and num.
8. If num modulo i is 0 then prime is False.
9. Once the second for loop is iterated through, the first for loop will ask if num is prime. If num is prime then it will be appended to the list, prime_list.
10. The method will be complete at this point and will return prime_list.
11. The method, print_prime is then called and prime_list is printed out.

The code for this function can be seen in the screenshot below:

To conclude, many of the algorithms for the interview questions are readily available on the internet, but they need to be checked to ensure they are correct. For instance, the code that I found on StackOverflow was not correct because it included 1 as a prime number whilst 1 is not generally considered a prime number. I, therefore, had to modify the code to ensure that if the number is 1 then prime becomes False.

Another disadvantage of the algorithms being readily available on the internet, the programmer is not encouraged to think through the algorithm for himself. It is important, therefore, that a person goes through the code with a fine-tooth comb to ensure the understands it and can replicate it if asked the question during a coding interview.

That’s it for this topic. Thank you for reading.

More content at plainenglish.io. Sign up for our free weekly newsletter. Get exclusive access to writing opportunities and advice in our community Discord.

Given an array arr[] of size N, the task is to rearrange the array elements such that all the Prime numbers are placed before the Non-prime numbers.

Examples:

Input: arr[] = {1, 8, 2, 3, 4, 5, 7, 20}
Output: 7 5 2 3 4 8 1 20
Explanation:
The output consists of all the prime numbers 7 5 2 3, followed by Non-Prime numbers 4 8 1 20.

Input: arr[] = {2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: 2 3 7 5 6 4 8 9 10

Naive Approach: The simplest approach to solve this problem is to make two arrays to store the prime and non-prime array elements respectively and print the prime numbers followed by the non-primes numbers. 

Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(N)

Alternate Approach: To optimize the auxiliary space of the above approach, the idea to solve this problem is using the Two-Pointer Approach. Follow the steps below to solve the problem:

• Initialize two pointers left as 0 and right to the end of the array as (N – 1).
• Traverse the array until left is less than right and do the following:
  • Keep incrementing the left pointer until the element pointing to the left index is Prime Number.
  • Keep decrementing the right pointer until the element pointing to the left index is a non-Prime Number.
  • If left is less than right then swap arr[left] and arr[right] and increment left and decrement right by 1.
• After the above steps, print the update array arr[].

Below is the implementation of the above approach:

C++

#include

using namespace std;

void swap(int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

bool isPrime(int n)

{

    if (n <= 1)

        return false;

    if (n <= 3)

        return true;

    if (n % 2 == 0 || n % 3 == 0)

        return false;

    for (int i = 5;

         i * i <= n; i = i + 6) {

        if (n % i == 0

            || n % (i + 2) == 0)

            return false;

    }

    return true;

}

void segregatePrimeNonPrime(

    int arr[], int N)

{

    int left = 0, right = N - 1;

    while (left < right) {

        while (isPrime(arr[left]))

            left++;

        while (!isPrime(arr[right]))

            right--;

        if (left < right) {

            swap(&arr[left], &arr[right]);

            left++;

            right--;

        }

    }

    for (int i = 0; i < N; i++)

        cout << arr[i] << " ";

}

int main()

{

    int arr[] = { 2, 3, 4, 6, 7, 8, 9, 10 };

    int N = sizeof(arr) / sizeof(arr[0]);

    segregatePrimeNonPrime(arr, N);

    return 0;

}

Java

import java.io.*;

import java.lang.*;

import java.util.*;

public class GFG {

    static boolean isPrime(int n)

    {

        if (n <= 1)

            return false;

        if (n <= 3)

            return true;

        if (n % 2 == 0 || n % 3 == 0)

            return false;

        for (int i = 5; i * i <= n; i = i + 6) {

            if (n % i == 0 || n % (i + 2) == 0)

                return false;

        }

        return true;

    }

    static void segregatePrimeNonPrime(int arr[], int N)

    {

        int left = 0, right = N - 1;

        while (left < right) {

            while (isPrime(arr[left]))

                left++;

            while (!isPrime(arr[right]))

                right--;

            if (left < right) {

                int temp = arr[right];

                arr[right] = arr[left];

                arr[left] = temp;

                left++;

                right--;

            }

        }

        for (int i = 0; i < N; i++)

            System.out.print(arr[i] + " ");

    }

    public static void main(String[] args)

    {

        int arr[] = { 2, 3, 4, 6, 7, 8, 9, 10 };

        int N = arr.length;

        segregatePrimeNonPrime(arr, N);

    }

}

Python3

def isPrime(n):

    if (n <= 1):

        return False

    if (n <= 3):

        return True

    if (n % 2 == 0 or n % 3 == 0):

        return False

    i = 5

    while (i * i <= n):

        if (n % i == 0 or n % (i + 2) == 0):

            return False

        i += 6

    return True

def segregatePrimeNonPrime(arr, N):

    left, right = 0, N - 1

    while (left < right):

        while (isPrime(arr[left])):

            left += 1

        while (not isPrime(arr[right])):

            right -= 1

        if (left < right):

            arr[left], arr[right] = arr[right], arr[left]

            left += 1

            right -= 1

    for num in arr:

        print(num, end = " ")

arr = [ 2, 3, 4, 6, 7, 8, 9, 10 ]

N = len(arr)

segregatePrimeNonPrime(arr, N)

C#

using System;

class GFG{

static bool isPrime(int n)

{

    if (n <= 1)

        return false;

    if (n <= 3)

        return true;

    if (n % 2 == 0 || n % 3 == 0)

        return false;

    for(int i = 5; i * i <= n; i = i + 6)

    {

        if (n % i == 0 || n % (i + 2) == 0)

            return false;

    }

    return true;

}

static void segregatePrimeNonPrime(int[] arr, int N)

{

    int left = 0, right = N - 1;

    while (left < right)

    {

        while (isPrime(arr[left]))

            left++;

        while (!isPrime(arr[right]))

            right--;

        if (left < right)

        {

            int temp = arr[right];

            arr[right] = arr[left];

            arr[left] = temp;

            left++;

            right--;

        }

    }

    for(int i = 0; i < N; i++)

        Console.Write(arr[i] + " ");

}

public static void Main(string[] args)

{

    int[] arr = { 2, 3, 4, 6, 7, 8, 9, 10 };

    int N = arr.Length;

    segregatePrimeNonPrime(arr, N);

}

}

Javascript