Categories > WeAreDevs > Hangout >

CodeWars V2 in any language

pooperlegend

Posts: 39

Threads: 8

Joined: Jun, 2023

Reputation: 0

Posted

make a program which will get how many prime numbers there are in 1 million then keep doing that for 5 seconds give or take a few miliseconds and then list how many times it was able to do that.

Rules
you can only use the Sieve of eratosthenes algorihim
multithreading is allowed but limited to 32 threads
you must show how long it took and how many passes in the console

Good Luck my fellow coders!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  • 0

https://media.discordapp.net/attachments/1074297826219139153/1118491534581567568/Mask_group.png

LogiSec

Something Random

Posts: 54

Threads: 2

Joined: Mar, 2023

Reputation: 6

Replied

Lua(JIT) :sunglasses:
https://cdn.discordapp.com/attachments/1113868407713054821/1121415689916395550/image.png

local sieve = {}
local count = 1
local sTime = os.clock()
local passes = 0

repeat
    for i = 1, 1000000 do
        sieve[i] = true
    end

    for i = 2, 1000000 do
        if sieve[i] then
            count = count + 1

            for k = i * 2, 1000000, i do
                sieve[k] = false
            end
        end
    end

    passes = passes + 1
until os.clock() - sTime >= 5

local eTime = os.clock()
local elTime = eTime - sTime

print("Time: " .. elTime .. "s")
print("Passes: " .. passes)

  • 0

Zayn

.zayn0 (Previously B00M)

vip

Posts: 306

Threads: 16

Joined: Jul, 2022

Reputation: 10

Replied

Good start, giving y'all something competent to beat:

https://media.discordapp.net/attachments/1097948107741876355/1121417178034491453/image.png?width=410&height=98

 

Code (Go):

package main

import (
    "fmt"
    "time"
)

func countPrimes(limit int) int {
    bitArraySize := (limit + 1) / 2
    isComposite := make([]bool, bitArraySize)

    primeCount := 0

    sqrtLimit := intSqrt(limit)
    for number := 3; number <= sqrtLimit; number += 2 {
        if !isComposite[number/2] {
            for multiple := number * number; multiple <= limit; multiple += 2 * number {
                isComposite[multiple/2] = true
            }
        }
    }

    for _, composite := range isComposite {
        if !composite {
            primeCount++
        }
    }

    return primeCount
}

func intSqrt(x int) int {
    if x < 0 {
        panic("Cannot compute square root of a negative number.")
    }

    if x < 2 {
        return x
    }

    guess := x / 2
    for guess*guess > x {
        guess = (guess + x/guess) / 2
    }

    return guess
}

func main() {
    const duration = 5 * time.Second
    const limit = 1000000

    startTime := time.Now()
    endTime := startTime.Add(duration)

    primeCount := 0
    runCount := 0

    for time.Now().Before(endTime) {
        primeCount = countPrimes(limit)
        runCount++
    }

    fmt.Printf("Total runs: %d\n", runCount)
    fmt.Printf("Prime numbers found: %d\n", primeCount)
    fmt.Printf("Elapsed time: %s\n", time.Since(startTime))
}

Comments

LogiSec 6 Reputation

Commented

You win, I quit.."walking away crying"

  • 0

Zayn 10 Reputation

Commented

thanks gg /charss

  • 0

  • 0

#Road to 15 Rep

https://media.discordapp.net/attachments/1081737726048608379/1088936664941989979/WRDBanner3.png

PC Specs: RTX 4080 OC (16GB), 32 GB 3200MHz, i7-11700k

pooperlegend

Posts: 39

Threads: 8

Joined: Jun, 2023

Reputation: 0

Replied

@B00M
ignore the extra 0.1 second idk why thats happening its hard coded to stop exactly at 5 seconds
https://cdn.discordapp.com/attachments/1065628036994715679/1121457757464313866/image.png


#include <iostream>
#include <vector>
#include <chrono>
#include <thread>
#include <atomic>

using namespace std;
using namespace std::chrono;

const int limit = 1000000;
const int numThreads = 48;

void sieveThread(vector<char>& sieve, atomic<int>& passes) {
    while (true) {
        int p = 2;
        for (; p * p <= limit; p++) {
            if (sieve[p]) {
                for (int i = p * p; i <= limit; i += p) {
                    sieve[i] = false;
                }
            }
        }
        passes++;
    }
}

int main() {
    int count = 0;
    atomic<int> passes(0);

    vector<char> sieve(limit + 1, true);
    vector<thread> threads;

    for (int i = 0; i < numThreads; i++) {
        threads.emplace_back(sieveThread, ref(sieve), ref(passes));
    }
    auto startTime = high_resolution_clock::now();

    this_thread::sleep_for(seconds(5));
    for (auto& thread : threads) {
        thread.detach();
    }

    auto endTime = high_resolution_clock::now();
    auto elapsedTime = duration_cast<duration<double>>(endTime - startTime).count();

    for (int i = 2; i <= limit; i++) {
        if (sieve[i]) {
            count++;
        }
    }
    cout << "Time: " << elapsedTime << "s" << endl;
    cout << "Passes: " << passes << endl;
    cout << "Prime numbers found: " << count << endl;

    return 0;
}

  • 0

https://media.discordapp.net/attachments/1074297826219139153/1118491534581567568/Mask_group.png

Zayn

.zayn0 (Previously B00M)

vip

Posts: 306

Threads: 16

Joined: Jul, 2022

Reputation: 10

Replied

@pooperlegend You said 32 threads was limit smh so in return I will also have 48 threads.

https://media.discordapp.net/attachments/1097948107741876355/1121476982891347968/image.png?width=398&height=75

Now perish as I finally finished writing mine. Go is clearly more powerful

 

Code (Go):

package main

import (
    "fmt"
    "runtime"
    "sync"
    "time"
)

func countPrimes(limit int, wg *sync.WaitGroup, primeCount *int) {
    defer wg.Done()

    bitArraySize := (limit + 1) /2
    isComposite := make([]bool, bitArraySize)

    sqrtLimit := intSqrt(limit)
    for number := 3; number <= sqrtLimit; number += 2 {
        if !isComposite[number/2] {
            for multiple := number * number; multiple <= limit; multiple += 2 * number {
                isComposite[multiple/2] = true
            }
        }
    }

    localCount := 0
    for _, composite := range isComposite {
        if !composite {
            localCount++
        }
    }

    runtime.LockOSThread()
    *primeCount += localCount
    runtime.UnlockOSThread()
}

func intSqrt(x int) int {
    if x < 0 {
        panic("Dumb-ass you cannot squareroot negative numbers.")
    }

    if x < 2 {
        return x
    }

    guess := x / 2
    for guess*guess > x {
        guess = (guess + x/guess) / 2
    }

    return guess
}

func main() {
    const duration = 5 * time.Second
    const number = 1000000
    const goroutines = 48

    startTime := time.Now()
    endTime := startTime.Add(duration)

    runCount := 0
    primeCount := 0

    var wg sync.WaitGroup
    wg.Add(goroutines)

    for i := 0; i < goroutines; i++ {
        go countPrimes(number, &wg, &primeCount)
    }

    for time.Now().Before(endTime) {
        runCount++
    }

    wg.Wait()

    fmt.Printf("Total passes: %d\n", runCount)
    fmt.Printf("Elapsed Time: %s\n", time.Since(startTime))
}

  • 0

#Road to 15 Rep

https://media.discordapp.net/attachments/1081737726048608379/1088936664941989979/WRDBanner3.png

PC Specs: RTX 4080 OC (16GB), 32 GB 3200MHz, i7-11700k

pooperlegend

Posts: 39

Threads: 8

Joined: Jun, 2023

Reputation: 0

Replied

@B00M the testing results were tested on 32 threads i was modifying the code to check for bugs later so yeh mine was tested on 32 threads

 

  • 0

https://media.discordapp.net/attachments/1074297826219139153/1118491534581567568/Mask_group.png

Users viewing this thread:

( Members: 0, Guests: 2, Total: 2 )