Day 25: Running Time and Complexity

Sort by

recency

|

809 Discussions

|

  • + 0 comments
    C# Csharp
    
        static void Main(String[] args) 
        {
            int row = int.TryParse(Console.ReadLine(), out int inputRow) ? inputRow : 0;
    
            while (row > 0)
            {
                int.TryParse(Console.ReadLine(), out int rec);
    
                if (rec > 1)
                {
                    bool isPrime = true;
    
                    // Optimized primality test: check divisors only up to the square root
                    for (int i = 2; i * i <= rec; i++)
                    {
                        if (rec % i == 0)
                        {
                            isPrime = false;
                            break;
                        }
                    }
    
                    string result = isPrime ? "Prime" : "Not prime";
                    Console.WriteLine(result);
                }
                else
                {
                    Console.WriteLine("Not prime");
                }
    
                row--;
            }
        }
    
  • + 0 comments
    def isprime(p):
        if p <= 1:
            return 'Not prime'
        if p <= 3:
            return 'Prime'
        if p % 2 == 0 or p % 3 == 0:
            return 'Not prime'
        i = 5
        while i * i <= p:
            if p % i == 0 or p % (i + 2) == 0:
                return 'Not prime'
            i += 6
        return 'Prime'
    
    x = int(input())
    for _ in range(x):
        p = int(input())
        print(isprime(p))
    
  • + 0 comments

    import java.io.; import java.util.;

    public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan= new Scanner(System.in);
    
        int casos= scan.nextInt();
    
        for (int i = 0; i < casos; i++) {
            int number= scan.nextInt();
    
             if(number<=1){
            System.out.println("Not prime");
        }else{
        boolean esPrimo=true;
    
        for (int j = 2; j <= Math.sqrt(number); j++) {
            if(number%j==0){
                esPrimo=false;
                break;
            }   
        }
        if(!esPrimo){
            System.out.println("Not prime");
        }else{
            System.out.println("Prime");
        }
    
        }
    
    }
        }
    

    }

  • + 0 comments
    import math
    
    def is_prime(n: int) -> str:
        if n == 1:
            return "Not prime"
        ans = (
            next(
                filter(
                    lambda x: n % x == 0,
                    (div for div in range(2, math.floor(math.sqrt(n) + 1)))
                ), None
            )
        )
        return "Prime" if ans is None else "Not prime"
        
    tests = [int(input()) for i in range(int(input()))]
    for test in tests:
        print(is_prime(test))
    
  • + 0 comments

    Java Solution

     Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            for(int j=n;j>0;j--)
            {
                int a = sc.nextInt();
                boolean pr = true;
                if(a==1)
                {
                    System.out.println("Not prime");
                    continue;
                }
                for(int i=2;i<=a/2;i++)
                {
                    if(a%i==0)
                    {
                        pr = false;
                        System.out.println("Not prime");
                        break;
                    }
                }
                if(pr==true)
                {
                        System.out.println("Prime");
                    
                }
            }